Automata Grammar Questions: Hi there, I have been stuck on these problems, I onl

Question

Automata Grammar Questions:

Hi there, I have been stuck on these problems, I only ask for assistance on one of them even though they are both displayed, but if you help with both of them with some explaination that would be great! Any help is greatly appreciated! Thanks!

Let L be the language of the grammar: S AB A aAb I aA I E B bBa I c The operation min returns those strings in L such that no proper prefix is in L. Determine the language min and identify in the list below the one string that is in min a) abbbcaa. O b) abbbbbca O c) aaaabca O d) aabbbbca A linear grammar is a context-free grammar in which no production body has more than one occurrence of one variable. For example, A 0B1 or A 001 could be productions of a linear grammar, but A BB or A A0B could not. A linear language is a language that has at least one linear grammar. The following statement is false: "The concatenation of two linear languages is a linear language." To prove it we use a counterexample: We give two linear languages L1 and L2 and show that their concatenation is not a linear language Which of the following can serve as a counterexample? a) L (w w anbn, where n is a positive integer L2 w (aa) (bb) where n is a positive integer) b) L1 (wiw n-1 (ab), where n is a positive integer L2 W (aaa)n. where n is a positive integer O C L1 W WRaaa (aaa) 1 (ab) where n is a positive integer L2 (ww (aaa)ncndn, where n is a positive integer O d) L1 (ww aaa(aba) (ab) where n is a positive integer) L2 W WRC (aaa)n. where n is a positive integer)

Explanation / Answer

C is the correct answer.

1. S->AB

2. ->AbBa

3. ->Abca

4. ->aAbca

5. ->aaAbca

6. ->aaaAbca

7. ->aaaaAbca

8. ->aaaaebca

9 ->aaaabca

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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