Given the following grammar s rightarrow s[s] s rightarrow Construct a leftmost

Question

Given the following grammar s rightarrow s[s] s rightarrow Construct a leftmost and rightmost derivation for the string Find a grammar for each of the following languages. Provide brief explanations on how you came up with the solution. {b^n a | n = 0, 1, 2, ...} {a^n bc^n | n = 0, 1, 2, ...} {a^m bc^n | n = 0, 1, 2, ... and m = 0, 1, 2, ...} {a^m b^n | n = 1, 2, ... and m = 0, 1, 2, ...} Let L = { abb, b} and M = {bba, ab, a}. What is ML? For each of the following equation, solve for the language L. Provide brief explanations on how you came up with the solutions. L{a, b} = {a, baa, b, bab} L{ a} = { a, b, ab, ba, aba} L{b, ab} = {abb, ab, abab, bab, b, bb}

Explanation / Answer

i)Left most Derivation

S[S]

[S]

[S[S]]

[S[S][S]]

[[S][S]]

[ [ ] [ S[S] ] ]

[ [ ] [ [ ] ] ]

Right most Derivation:

S

S[S]

S[S[S] ]

S[ S [ S[ S ] ] ]

S [ S [ S [ ] ] ]

S [ S [ [ ] ] ]

S [ S[ S] [ [ ] ] ]

S [ S [ ] [ [ ] ] ]

S [ [ ] [ [ ] ] ]

[ [ ] [ [ ] ] ]

2) bna n = 0,1 ,2 ,.

S -> BA

A -> a

B -> Bb |

if n = 0

S -> BA

-> a

if n=1

S ->BA

->Bba

->ba

S-> BA

-> Bba

-> Bbba

-> bba

ii)anbcn

A  >   aAc  | b

n=0

A -> b

n=1

A -> aAc

-> abc

n=2

A -> aAc

-> aaAcc

-> aabcc

iii)

S->ABC

A-> Aa |

B -> b

C -> Cc |

iv) S -> AB

A -> Aa |

B -> Bb |

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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