Question

3. [20 points] Give short answers to each of the following parts. Each answer should be at most three sentences. Be sure to define any notation that you use. (a) Explain the difference between a DFA and an NFA. (b) Give a regular expression for the language consisting of strings over the alphabet 2-(0, 1) that contains an even number of 0's and an odd number of 1's and does not contain the substring 01. (c) Give the formal definition of the transition function of a PDA. (d) Suppose that language A, is recognized by NFA N, below, and language Az is recognized by NFA N, below. Note that the transitions are not drawn in N1 and N2. Draw a picture of an NFA for A Az N1 N2

Answer 1

3.

(a)The differences between DFA and NFA are as follows :

DFA(Deterministic Finite Automata)	NFA(Non Deterministic Finite Automata)
In DFA,conversion of regular expression to DFA is complex.	In NFA,the conversion of regular expression to NFA is easy when compared to DFA.
DFA requires more memory for storing the state information.	NFA requires more computations to match with the regular expression input.
Back tracking is allowed in DFA	Back tracking is not always allowed in NFA
The integer for the next state is 1	The integer for the next state can be either 0 or 1
All DFA's can be NFA's	All NFA's are not DFA's

(c)

A PDA (Push Down Automata) can be defined as a state machine(finite) which consists of an additional stack in the storage.In short it can be described as a 7-tuple.The formal definition is as follows :

Date M (a,8, F, Ain,Vin A Qfinite set of states 8 1 finite Subset of Qx (AUSAH)XTXQXF* F-Set of fin al states Ain initial stack symbel ie Aine in initial state ie lin E Q where an alphatet of inpit Symbols A

(d)

Subje N2 O Given A is the longuege recogrised 6 NFA N, i N-(a,,8,1, F Given Ar is the anguage recoisd by NFA N ie N2(,, 8, n, F N will be N- (Q,, 8,4,, F N FA fox A,o A Let us say EQ, 8 satis fies the following if vea,-FI 8, A, a)if EF ,ate &C)Ut EF, ,a= E if&EQr

Date N