Quiz 1 (COMP3560)-Automata and Formal Languages Solve the following problems. Pl

Question

Quiz 1 (COMP3560)-Automata and Formal Languages Solve the following problems. Please write your answers in 1. Consiera set of simbols _la readable and clean form. (1) Find all strings in * shorter than 3. 2) Let L , ab), Is L a language on 7 Why? (3) Write L and 2. Let (0.1). What languages do the following grammar generated? Write the languages S-AB a grammar that generates language L-a"b:m,n20) (2) Find a grammar that generates language L-{b"a":n 20 } . (3) Find a grammar that generates language L-bamz n ). 4. (1)Draw a transition graph for the dia M-Q.,8,9.,F), where Q-9..q,41, Z-(a, b), F {%-%) and is definded as (2) Give the language accepted by the above dfa.

Explanation / Answer

1
(1) lambda, a, b
are the words that can be created shorter than 2

(2) Yes, {lambda, ab} is a language since it contains one or more words created using symbols if the language

(3) considering L = {lambda, ab}
L0 = {lambda}
L3 = {lambda, ab, abab, ababab}

2
S = AB
A = 0A1|lambda //So A creates a wordstring of n zeros followed by n ones
B = B1 | lambda //So B produces one or more ones

So generally
Language recognized by S is 0m1n, where m <= n

3
1
S -> AB
A -> 0A | lambda
B -> 1B | lambda

2
S -> bbA
A -> bAa | lambda

3
S -> BA
A -> bAa | lambda
B -> bB | lambda

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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