Attach This Question Paper on Top of Your Answer Sheets

Attach This Question Paper on Top of Your Answer Sheets

Attach This Question Paper on Top of Your Answer Sheets

Type Your Name Here:

CSE 5210Formal Languages and Automata TheorySpring 2015Exam 3

Points 50Time 70 min

REMEMBER THIS IS JUST A KEY, NOT THE EXACT ANSWER

(1)How many strings of sizes 0, 1, 2, 3 and 4 can be there for Sigma={a, b, c}?[No relation to the language in the following question.]

What is the language generated with the following grammar over Sigma={0,1,2,3}? (No proof necessary.)

S-> 0S2 | P |ϵ

P -> 1P2 | Q |ϵ

Q -> 1Q3 | ϵ

Generatethe string 00113222 using the grammar[4+2+4]

3^0 +3^1 +3^2 +3^3 + 3^4, for |Sigma| =3;

0n1k1m3m2k2n, that is 0n1k+m3m2n+k

(2) Pumping lemma:[10]

Prove that the following language is not a Context Free Language. Sigma={a,b,c}

{a2nb2m c3n | m,n ≥ 1 and m=n}

Note, m=n, so ignore m, replace it with n.

Asymmetry on power of c is immaterial, any pumping of a’s, b’s and/or c’s must maintain the exactproportion 2:2:3, that PL will cause violation.

  • Assume a CFG CNF G with p non-terminals for the language.
  • Pick a string s = a^2N b^2N c^3N, for 2N>=2^p.
  • Pumping Lemma applies because |s| > 2^p.
  • Write down the PL with s=uvwxy, and the length restrictions.
  • Run vwx substring over s, for two types of cases: vwx on (1) pure parts (a’s or b’s or c’s), and (2) on boundary parts (ab, or bc boundary).
  • Asymmetric strings must be generated by the grammar G that cannot be in the language.
  • Hence, contradiction. No such Grammar G exists. So, the language is not a CFL.

(3) PDA:

Develop a PDA for the language overSigma={a, b, c}

{an bmcn+m| n,m ≥ 0}

Run one in-language string, and one out-of-language string over your PDA. [6+4]

CFG is easy! S->aSc | P | e, P->bPc | e

But that is not the question, unless you can convert it to a GNF and then translate.

For PDA, it is easy to push on stack a symbol for each ‘a’and ‘b’ read, and pop for ‘c’. Handle carefully for accepting epsilon.

(4) Write a PDA for the language {anbcn | n>=1}

Run the string aaac with your PDA.[6+4]

Push for a’s, ignore b, then pop for c’s. Note, no epsilon.

aaac should be rejected with stack being not empty at the end of string.

(5) Run the following PDA (only valid delta is given here) on strings: (1) aab , (2) aaab

Δ:

Δ (q1, a, #) = (q2, A#)

Δ (q2, a, A) = (q1, A)

Δ (q1, a, A) = (q2, AA)

Δ (q2, a, A) = (q1, A)

Δ (q1, b, A) = (q3, e)

Δ (q3, e, #) = (q3, e)

What is the corresponding language accepted by this machine?[3+3+4]

You guessed it correct, original intention was:

a2nbn or a2n+1bn+1

That needed delta(q3, b, A) = (q3, e), which is missing.

Also, adding delta(q1, e, #) = (q3, e) will let epsilon be accepted.

However, the correct language for the above automaton is: {aab} only, nothing else.

So, aab gets accepted, and aaab gets rejected.