Sunday, December 18, 2011

NFA Question List

Non-Deterministic Finite Automata Question List

Question List - I




Q.1
(a)

Find out Regular Expression for Given Finite Automaton.
10
Q.2
(a)
Give the Recursive Definition of δ* for an NFA.

Using Subset Construction Draw FA for Given.
5

(b)
If L subset of Σ* is a Language that is accepted by the NFA – Λ              M=(Q, Σ, q0, A, δ), then there is an NFA M1=(Q1, Σ, q1, A1, δ1) that also accepts L.
5


OR


(b)
Define Acceptance by an NFA.

Check Whether the following strings are accepted by NFA or not.
(1) abab         (2)  aaabbb
5



Question List - II




Q.1
(a)
Do as Directed.



(i)   Explain Relationship between DFA and NFA.
2


(ii)  Write down Statement & Application of Kleene’s Theorem  Part - I.
2


(iii) Non Recursive Definition of δ* for an NFA.
1

(b)
Prove that The Language accepted by any Finite Automata is Regular.
5
Q.2
(a)
Define δ* for an NFA-Λ Recursively.

Using Algorithm Draw an NFA accepting the same Language.
5

(b)
Define Λ – Closure of a Set of States for NFA-Λ.
A Transition table is given for an NFA- Λ with Seven States.

q
δ(q, a)
δ(q, b)
δ(q, Λ)
1
ø
ø
{ 2 }
2
{ 3 }
ø
{ 5 }
3
ø
{ 4 }
ø
4
{ 4 }
ø
{ 1 }
5
ø
{ 6, 7 }
ø
6
{ 5 }
ø
ø
7
ø
ø
{ 1 }

Find:   (i)   Λ ({3,4})    (ii)    δ*(1, ab)
5


OR


(b)
Convert Given NFA in to Equivalent DFA Using Subset Construction Method.

5


No comments:

Post a Comment