Context-free Languages and Turing Machines

Question 1.(a) Consider the language

{aⁱb^kc^m |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:

G₁ : S → SaS | SbS | c

G₂ : S → DAd
A → aS | ε

B → bD | ε

D → cB

(a) Draw two different parse trees for the word cacbc and the grammar G₁.

(b) Give the LOOKAHEAD set for every rule of grammar G₂.

(c) Is the grammar G₂ LL(1) ?

(d) Give the set of nullable nonterminals for the grammar G₂.

(e)Give the context-free grammar that you obtain from replacing all ε-rules in gram-mar G₂

Question 3. (a) Consider the following Turing machine with input alphabet {a, b} and tape al- phabet {a, b, _}:

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.