I need help with Computer Theory. Answer the questions that have marks. Thanks C

Question

I need help with Computer Theory. Answer the questions that have marks. Thanks

Construct a right-linear grammar for the language L((aab*ab)*). Find a regular grammar that generates the language on sigma = {a, b} consisting of the strings with no more than three a's. In Theorem 3.5, prove that L(G) = (L(G))^R. Suggest a construction by which a left-linear grammar can be obtained from an nfa directly. Find a left-linear grammar for the language in Exercise 6 Find a regular grammar for the language L = P{a^n b^n: n + m is even} Find a regular grammar that generates the language L = {w elementof {a, b}^n: n_e (w) + 3n_b (w) is even} Find regular grammars for the following languages on {a, b} (a) L = {w:n_a(w) and n_b (w) are both even} (b) L = {w:(n_a(w) - n_b(w)) mod 3 = 1}. (c) L = {w: (n_a(w) - bn_b (w)) mod 3 notequalto 1}. (d) L = {w: (n_a(w) - n_b (w)) mod 3 notequalto 0}. (e) L = (w: |n_a(w) - n_b (w)| is odd}. Show that for every regular language not containing lambda there exists a rightlinear grammar whose productions are restricted to the forms A rightarrow aB or A rightarrow a, where A, B elementof V, and a elementof T. Show that any regular grammar g for which L(G) notequalto must have at least one production of the form A rightarrow x where A elementof V and x elementof T*. Find a regular grammar that generates the set of all real numbers in C. Let G_1 = (V_1 sigma_1 S_1 P_1) be right-linear and G_2 = (V_2, sigma, S_2, P_2) be a left linear grammar, and assume that V_1 and V_2 are disjoint. Consider the linear grammar G = ({S} V_1 V_2, sigma, S, P), where S is not in V_1 V_2 and P = {S rightarrow S_1|S_2} P_1 P_2. Show that L(G) is regular.

Explanation / Answer

6. L((aab*ab)*)

Ans : G = (V, T, S, P)
S -> aaA|
A -> bA|abS

7. regular grammer consists of all strings with no more than three a's

Ans :G=(V,T,S,P), where
V= {S,A,B},
T={a,b},
P={S->bS|aA|, A->bA|aB|, B->bB|aC|,C->bC|}

  The derivation of a string babbaab:
S => bS => baA => babA => babbA =>=> babbaB=> babbaaC => babbaabC => babbaab

11. Find a regular grammer for the language L= {a^n b^m : (n + m) is even}.

Ans: A->AB
A->aaA/a/
B->bbB/b/

13 a) Regular grammer for L= {w:na(w) and nb(w) are both even}

Ans:S ->
S -> Aab
A -> Ab
A -> Saa

b) Regular grammer for L= {w:na(w)-nb(w) mod 3 =1}

Ans :G = (V , T , S, P ), where
V = {S,A,B},
T={a,b},
P={S -> aA|bB,A->aB|bS|,B->aS|bA}
The derivation of a string abaaaaba:
S -> aA -> abS -> abaA -> abaaB -> abaaaS-> abaaaaA -> abaaaabS -> abaaaabaA -> abaaaaba

c) Regular grammer for L= {w:na(w)-nb(w) mod 3 != 1}

Ans: S -> A|AaAaA|AbAbA.
A -> aAb|bAa|.

d) regular grammer for L= {w:na(w)-nb(w) mod 3 != 0}

Ans: S -> A|AaAaA|AbAbA
A-> aAb|bAa|a|b

e) Regular grammer L = {w : |na(w) nb(w)| is odd }.

Ans: S -> AaA|AbA.
A -> aAb|bAa|

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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