Hi, I am having trouble answering the following question. Let L = { a n b 2n c m

Question

Hi,

I am having trouble answering the following question.

Let
L = { anb2ncm | m >= 1, n >= 1 }

Using the context-free grammar designed for L as a template, design another context-free grammar for the language (denoted as Lpref) of all strings that are prefixes of the strings L,
i.e. Lpref = {x | x is a prefix of a string in L }.
Note, by this definition, each string in L will generate multiple strings in Lpref. For example, the string abbcc, which is in L, will generate the following list of strings in Lpref: {epsillon, a, ab, abb, abbc, abbcc}.

Any help you can provide would be very much appreciated.

Explanation / Answer

L = { anb2ncm | m >= 1, n >= 1 }

the prefix of anb2ncm will be as follow

1. any no of of a'a

2. any no of a followed by no of b's which is less or equal to the two times of a's

3, any no of a followed by no of b's which is two times the no of a's followed by any no of c idea is whenever c will come then there is 2's b as a.

we can write

Lpre ={apbqcr | p=0 and q=0 and r=0 OR p>=1 and q=0 and r=0 OR P>=1 and 1<=q<=2p and r=0 or P>=1 and q=2p and r >=1}

for above language we can write CFG as follow

S is start variable.

S-->epsilon

above productionwill satisfy (p=0 and q=0 and r=0)

S-->A

A-->aA | a

(above two production will staisfy p>=1 and q=0 and r=0)

S--> BC

B-->aB | a

C-->aCb | aCbb | ab | abb

(above three production will staisfy P>=1 and 1<=q<=2p and r=0)

S-->DF

D-->aDbb | abb

F-->cF | c

(above three production will staisfy P>=1 and q=2p and r>=1)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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