### 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.
Find: (i) Λ ({3,4}) (ii) δ*(1, ab) | 5 | ||||||||||||||||||||||||||||||||

| | OR | | ||||||||||||||||||||||||||||||||

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

## Comments

## Post a Comment