Construct right- and left-linear grammars for the language L = {a^n b^m: n great

Question

Construct right- and left-linear grammars for the language L = {a^n b^m: n greaterthanorequalto 3, m greaterthanorequalto 2}. For sigma = {a, b}, find regular expressions for the complement of the following languages L = L(aa*bb*). Use the construction in Theorem 4.1 to find nfa's that accept L(b*aab*) Intersection L(baa*). a) Given a regular language L and a string w elementof L, show how one can determine if w^R elementof L. b) Show that there exists an algorithm for determining if L_1 is a proper subset of L_2, for any regular languages L_1 and L_2. Show that the language L = {a^n b^k c^n: n greaterthanorequalto 0, k greaterthanorequalto 0}is not regular. Determine whether or not the following languages are regular. a) L = {a^n b^n: n greaterthanorequalto 1} Union {a^n b^m: n greaterthanorequalto 1, m greaterthanorequalto 1} b) L = {a^n b^n: n greaterthanorequalto 1} Union {a^n b^n + 2: n greaterthanorequalto 1}.

Explanation / Answer

SINGLE TERMINAL: If the RE is simply e (e being any terminal), we can write G, with only one production rule S --> e (where S is the start symbol), is an equivalent RG.

UNION OPERATION: If the RE is of the form e + f, where both e and f are terminals, we can write G, with two production rules S --> e | f, is an equivalent RG.

CONCATENATION: If the RE is of the form ef, where both e and f are terminals, we can write G, with two production rules S --> eA, A --> f, is an equivalent RG.

STAR CLOSURE: If the RE is of the form e*, where e is a terminal and * Kleene star closure operation, we can write two production rules in G, S --> eS | ^, is an equivalent RG.

PLUS CLOSURE: If the RE is of the form e+, where e is a terminal and + Kleene plus closure operation, we can write two production rules in G, S --> eS | e, is an equivalent RG.

STAR CLOSURE ON UNION: If the RE is of the form (e + f)*, where both e and f are terminals, we can write three production rules in G, S --> eS | fS | ^, is an equivalent RG.

PLUS CLOSURE ON UNION: If the RE is of the form (e + f)+, where both e and f are terminals, we can write four production rules in G, S --> eS | fS | e | f, is an equivalent RG.

STAR CLOSURE ON CONCATENATION: If the RE is of the form (ef)*, where both e and f are terminals, we can write three production rules in G, S --> eA | ^, A --> fS, is an equivalent RG.

PLUS CLOSURE ON CONCATENATION: If the RE is of the form (ef)+, where both e and f are terminals, we can write three production rules in G, S --> eA, A --> fS | f, is an equivalent RG

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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