Friday, May 14, 2010

Unit - III Question List

Question List - I
Q.1
(a)
Do as Directed.



(i)   Give the Difference: DFA Vs. NFA
2


(ii)  Non Recursive Definition of δ* for an NFA-Λ
1


(iii) Draw NFA for given below.
(1)  (a + b)* bb (a + b)*
(2)  L = { x / x start with substring 101 }
2

(b)
For any NFA M=(Q, Σ, q0, A, δ) accepting a language L subset of Σ*, there is an FA M1=(Q1, Σ, q1, A1, δ1) that also accepts L.
5
Q.2
(a)
Define NFA.
Calculate the Following.
(i)   δ*(1,aabbab)       (ii)   δ*(1,bab)
5

(b)
Draw NFA-Λ for following.
(1) aa (ba)* + b*aba*    (Do Not Simplify the Answer)
(2) (00 + 1)* (10)*         (With Simplified Form)
5


OR


(b)
Using Algorithm Draw an NFA accepting the same Language.
5