At Flat HMP-1
At Flat HMP-1
At Flat HMP-1
1. Compare FA, NFA and NFA- Λ with illustration.For the following Regular Expression
draw an NFA-Λ recognizing the corresponding language.
(0 + 1) * (10+01) * 11
2. Consider the following NFA shown in Figure 1 and convert it into DFA
5. For the following Regular Expression draw an NFA- Λ recognizing the corresponding
languages.
(i) (00 + 1) * (10) *
(ii) 001 * 0 * 11
9. An NFA with states 1-5 and input alphabet {a, b} has the following transition table.
Q δ(q, a) δ(q, b)
1 {1, 2} {1}
2 {3} {3}
3 {4} {4}
4 {5} Ø
5 Ø {5}
1. Draw a transition diagram.
2. Calculate δ*(1, ab).
3. Calculate δ*(1, abaab).
10. A transition table is given for an NFA-^ with seven states.
Find:
1. ^({2, 3})
2. ^({1})
3. ^({3, 4})
4. δ*(1, ba)
5. δ*(1, ab)
6. δ*(1, ababa)
8. In each case, given the context-free grammar G, find a CFG G’ with no ^-productions and no
unit productions that generates the language L(G) – {^}.
a) G has productions
S → ABA A → aA | B → bB |
b) G has productions
S → aSa | bSb | A → aBb | bBa B → aB | bB |
c) G has productions
S →A| B | C A → aAa | B B → bB | bb C → aCaa | D
D → baD | abD | aa
7. Given the CFG G, find a CFG G’ in Chomsky Normal form generating L(G) – { Λ}
S->A | B | C
A->aAa | B
B->bB | bb
C->aCaa | D
D->baD | abD | aa
8. In each case, given the context free grammar G, find a CFG G’ in Chomsky normal form
generating L(G) – {^}.
G has the productions:
(1) S → AaA | CA | BaB A → aaBa | CDA | aa | DC
B → bB | bAB | bb | aS C → Ca | bC | D D → bD |^
(2) S → SS | (S) |^
(3) S → S(S) |^