Let: L_1 = {a^nb^2nc^m | m, n greaterthanequalto 1} L_2 = {x^nb^mc^2m | m, n gre

Question

Let: L_1 = {a^nb^2nc^m | m, n greaterthanequalto 1} L_2 = {x^nb^mc^2m | m, n greaterthanequalto 1} a) Give CFGs for L_1 and L_2. b) Is L_1 intersection L_2 a CFL? Justify your answer. c) Using the CFG designed for L_1 as a template, design another CFG for the language (denoted as L_pref) of all strings that are prefixes of the strings in L_1 - i.e., L_pref = {x | x is a prefix of a string in L_1} Note, by this definition, each string in L_1 will generate multiple strings in L_pref. For example, the string abbcc which is in L_1 will generate the following list of strings in L_pref:{elementof, a, ab, abb, abbc, abbcc}.

Explanation / Answer

L1={abbc,abbcc,aabbbbccc,aaaabbbbbbbbccccc}

L2={abcc,aabcc, aabbbcccc, aaaabbbbcccccccc}

The grammers for given regular expressions are given as.

1.S->aS1bbC/

S1->aS1bb/$   $ indicates the null

C->cC/€

2.S->aS1cc

S1->bB/€

B).L1intL2 =({}) after examinig above two languages there for phi is also as per CNF rules proven as CFL. Therefore this is also a CFL.

C).the language Lpref is given as={€,ab,abb,abbc,abbcc,} the CFG for given lpref is as follows:

S->a/ab/abb/abbc/abbS1/€

S1->cC/€

1.for first take the string aabbbbcccccc

S->aS1bbC

S->aS1bbC

S->aaS1bbbbC // S1->aS1bb(production used)

S->aabbbbC // S1-> null

S->aabbbbcC // C->cC

S->aabbbbccC //C->cC

S->aabbbbcccC //C->cC

S->aabbbbccccC

s->aabbbbcccc //C-null hence we get the string aabbbbcccc

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.