Uppercase (lowercase) letters stand for nonterminals (terminals) and S is the st

Question

Uppercase (lowercase) letters stand for nonterminals (terminals) and S is the start symbol in each grammar. For each of the 4 grammars listed above, indicate the language generated. Use exponential notation of symbols, where appropriate, and indicate explicit constraints on the exponents, when describing the following language sets. Also, you may enumerate the sentences in finite languages. Also, use the Kleene closure operator and set operators if necessary to completely describe the languages. Give a brief description of how you arrived at your answer. Formally describe each of the generated languages:

Explanation / Answer

a)
L(G1)

coming to all possibilities ..
S-> bSa = bca or bAa = bacd or simply c (since S->c)

So from above expression there was a chance that 'c' can comes first, but not always. so we use c
then followed by alteast one b and then pairs of 'c' and 'd'

So finally c, bc+d*a, bc*d*a

------------------------------------------------------------------------------------------------------------------------
(b) L(G2)
from first statement
S->bbAcccB
we can get .. expression must have alteast two b's and , 'A' can have series of b's and c's or simply 'b' since (A->bbAc|c)
So expression would be
L(G2) = bbb*cccc*c, bbb*cccc*cdc*

-------------------------------------------------------------------------------------------------------------------------------
(c) S -> abS | ab

this one is direct answer .. it contains series of ab pattern .. but contain atleast one
So under closure properties we can define
L(G3) = (ab)+

-------------------------------------------------------------------------------------------------------
(d)
L(G4)
..from above statement S -> Sc | Ec
we can consider .. we can have wither series of c's or terminal symbol ac, abc
So L(G4) is given by c+ac, abc, ac,abc

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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