UNIT I
1. Consider
the following ε–NFA. Compute the ε–closure of each state and find it’s
equivalent DFA.
ε
A b C
p Ф
{p} {q} Ф
q {p} {q} {r} Ф
*r {q}
{r} ф {p}
2. Construct
a NFA over the alphabet {0,1} that accepts all strings end in 01
3. For
the finite state machine M given in the following table, test whether the
strings 101101,11111 are accepted by
M.
4. Consider
the following ε–NFA. Compute the ε–closure of each state and find it’s
equivalent DFA.
ε
a b c
p {q,r} Ф {q} {r}
q Ф
{p} {r} {p,q}
*r Ф
ф ф ф
5. Convert
a NFA which accepts the string ends with 01 to a DFA.
6. Consider
the following ε–NFA. Compute the ε–closure of each state and find it’s
equivalent DFA.
ε
a b c
p {q} {p} Ф
Ф
q {r}
ф {q} Ф
*r Ф
ф ф {r}
7. Convert
the NFA string that ends with 01 to equivalent DFA
UNIT II
1. Find
The regular expression for the set of all strings denoted byR132 from the DFA
given below.
2. Draw
the table of distinguishabilities for this automaton & Construct the
minimum – state equivalent DFA.
3. Find
the regular expression for the set of all strings denoted by R133 from the deterministic finite automata given below
4. Construct
the NFA –Σ For the given regular expression Using Thompson’s and Construct DFA
For the above NFA –Σ and find the Minimized DFA? (b/a)*bba
5. Find
whether the languages (ww, w is in (1+0)*} and {1k | k=n2, n ≥1} are regular or
not.
UNIT III
1. Obtain
the regular expression that denotes the language accepted by the following DFA
2. Find
the regular expression for the set of all strings denotes by R13 3 from the deterministic finite automata
given below
3.
Find a derivation tree of a*b +a*b given that a*b+a*b is in L(G) where G
is given by
S → S + S | S * S , S → a |
b.
4.
Suppose the PDA P= ({q,p},{0,1},{Z0,X}, δ,q, Z0,{p}) has the following transition function :
1. δ(q,0, Z0) ={(q, XZ0)}
2. δ(q,0, X) = {(q,XX)}
3. δ(q,1, X) = {(q,X)}
4. δ(q,ε, X) = {(p,ε)}
5. δ(p,ε, X) = {(p,ε)}
6. δ(p,1, X) = {(p,XX)}
7. δ(p,1, Z0) = {(p,ε)}
starting from the intial ID (q,w, Z0), show all the reachable ID’s when
the input w is a)
01 b) 0011 c) 010.
UNIT IV
1. Show
that set of all strings over {a,b} consisting of equal number of a’s & b’s
is accepted by a deterministic PDA.
2. Convert
the grammar S → 0S1 | A, A→1A0 | S | ε
to a PDA that a accepts the same language by empty stack.
3. The
following grammar generates the language of regular expression 0*1(0+1)* S → A1B , A → 0A
| ε, B → 0B | 1B | ε. Give leftmost
& rightmost derivation of the
following strings: a) 00101 b) 1001
c) 00011
4. Design context free grammar for the
following languages
a) The set {0n1n | n≥1}, that is the
set of all strings of one or more 0’s followed by an equal number of 1’s.
UNIT V
1. Consider
the Language Lwwr={wwR | w is in
(0+1)*}. Design the PDA P to accept the Lwwr.
Starting from the initial ID (q,w, Z0), show all the reachable ID’s
when the input w is a) 11111 b) 0011 c) 011.
2. Convert
the PDA P= ({p,q},{0,1},{X,Z0},δ,q, Z0)
to a CFG , if is given by
1. δ(q,1, Z0) ={(q, XZ0)}
2. δ(q,1, X) = {(q,XX)}
3. δ(q,0, X) = {(p,X)}
4. δ(q,ε, X) =
{(q,ε)}
5. δ(p,1, X) = {(p,ε)}
6. δ(p,0, Z0) = {(q, Z0)}
3.
Prove the theorem, Let L be L(PF) for some PDA PF=(Q, ∑, Γ, δN, q,
Z0,F), then there Is
a PDA PN such that
L=L(PN)
4
Convert the PDA P= ({q,p},{0,1},{Z0,X}, δ,q, Z0,{p}) to a Context free
grammar.
1. δ(q,0, Z0) ={(q, XZ0)}
2. δ(q,0, X) = {(q,XX)}
3. δ(q,1, X) = {(q,X)}
4. δ(q,ε, X) = {(p,ε)}
5. δ(p,ε, X) = {(p,ε)}
6. δ(p,1, X) = {(p,XX)}
7. δ(p,1, Z0)
= {(p,ε)}
