Reference no: EM131766799
Context-free Languages and Turing Machines
Question 1.(a) Consider the language
{aibkcm |i ≥ 0, k ≥ 0, m ≥ 0, k = i + m}
Give a word that is in the language and a word that is not in the language.
(b) Give a context-free grammar for the language above.
(c) Use the Cocke-Younger-Kasami algorithm to determine whether abbaa is a word of the language of the following grammar. Give the table. State in one sentence whether the word is a word of the language of the grammar and how you obtain this conclusion from the table.
S → AX | BY | SS | BA
X → AS
Y → BS
A → a
B → b
(d) Give a parse tree for the word aaba with respect to the grammar above (for part (c)).
(e) What is FIRST( SS) with respect to the grammar above (for part (c)).
Question 2. Consider the following two context-free grammars:
G1 : S → SaS | SbS | c
G2 : S → DAd
A → aS | ε
B → bD | ε
D → cB
(a) Draw two different parse trees for the word cacbc and the grammar G1.
(b) Give the LOOKAHEAD set for every rule of grammar G2.
(c) Is the grammar G2 LL(1) ?
(d) Give the set of nullable nonterminals for the grammar G2.
(e)Give the context-free grammar that you obtain from replacing all ε-rules in gram-mar G2
Question 3. (a) Consider the following Turing machine with input alphabet {a, b} and tape al- phabet {a, b, _}:
![2105_turing machine.jpg](https://secure.expertsmind.com/CMSImages/2105_turing machine.jpg)
Give computations for the words ab and bb. State for each word whether the machine accepts it, rejects it or loops. If the machine loops, then give the first five configurations of the computation.
(b) Draw a Turing machine that decides the language of all words over the alphabet {a, b} that have an odd number of a's and an odd number of b's.