Draw two different parse trees for the word cacbc and the


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

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.

Request for Solution File

Ask an Expert for Answer!!
Theory of Computation: Draw two different parse trees for the word cacbc and the
Reference No:- TGS02562434

Expected delivery within 24 Hours