Question

Q1: Given the below language and context free gramma:, a. Show that the grammar is ambiguous using the string ( abc) by using substitutions. b. Then design a push down automata that recognizes the language. C. Then show the tracing of (abc, abbccc) using the push down automata. d. Then Show which two simple languages create the greaterlanguage. Give set builder notation for each language. e. Then produce Chomsky normal form for the grammar. The following context-free language is inherently ambiguous {a^bmc in=mVm=} It is generated by the following (ambiguous) grammar SAB A ACC BaBD C aCb E D DC E

Answer 1

A)-->

The given grammer is ambiguous grammar because we can derive abc string by two different substitution methods as follows;

B,C)-->

Push down automata for the given language is as follows and tracing of given strings also as follows;

Here I showed that abc string is accepted by PDA because in abc no.of a's=no.of b's

in the string abbccc either no.of a's!=no.of b's or no.of b's != no.of c's so which is not accepted by the given language.

D)-->

E)-->

Construction of CNF for the given grammar is long time taken process and i did not have that much of time to solve this last question but I can show you what will do for converting given grammar into CNF;

Process for converting grammar to cnf :

--> Eliminate start symbol from RHS.

-->Eliminate null, unit and useless productions.

--> Eliminate terminals from RHS if they exist with other terminals or non-terminals. e.g,; production rule X->xY can be decomposed as:

-->  Eliminate RHS with more than two non-terminals.

But I finally solved CNF for the given grammar as follows

I think it is right .if I did any mistakes please for give me.

Thankyou :)