B.tech. IV Sem (CSE), 2018-19

February 10, 2019

- Define a Finite Automaton. How you justify a modern computer as a
Finite Automata.

Ans: Definition: discussed in class. FA has no memory when compared with modern computer, and gives output as Yes/No. Has far less capabilities than a computer. - Describe the application of FA in building Lexical Analyzer for compilers.

Ans. A FA can recognize tokens in the first phase of a compiler, called lexical Analyzer. The tokens are, e.g., {, }, (, ), =, <, >, 2342, 123.5, begin, end, if, else, do, while, .... - Why a FA is deterministic? Justify your answer.

Ans. Because, for same input the output is always same, and that can be determined in advance, through the transition function of a FA. - For the alphabet set Σ = {a,b} construct DFAs for each of the following
languages.

(a) All strings with exactly one $a$.

Ans. Regex: $a$

(b) All strings with at least one $a$.

Ans. Regex: a(a + b)^{*}

(c) All strings with no more than three b’s.

Ans. a^{*}ba^{*}ba^{*}ba^{*}.

(Note: Construction of DFAs is straight forward from these regular expressions.) - Describe the language accepted by the automaton corresponding to the
transition diagram given in figure. Also, give its regular expression.

Ans. The required regular expressions is: 1^{*}(ϕ+0+01^{*}(00^{*}1)^{*}). A FA can be easily constructed based on this regular expression. - Construct the deterministic finite automaton for each of the following
languages:

(a){w|w ∈{a,b}^{*}and length of w is greater than 3}.

(b) {w∣w ∈{a,b}^{*}and every run of a has even length}.

{w∣w ∈{a,b}^{*}and number of as and bs are even in w}. - Find the finite automata for each of the following regular expressions:

(a) aa^{*}bb^{*}cc^{*}

(b) (aba^{*}ba^{*}b)^{*}

(c) a^{*}b + (b^{*}a)^{*}

(d) (aaa)^{*}b + (aa)^{*}b

(Note: The The solution is straight forward, as similar exercises have been discussed in class.) - Show that for a DFA, for every q ∈ Q, a ∈ Σ, δ(q,a) = q, prove that
δ
^{*}(q,x) = q, for every x ∈ Σ^{*}.

Ans. The δ^{*}is iteration of δ, hence the proof. - Show that there cannot be a DFA of less than four states which can
recognize the language: {w ∈{a,b}
^{*}∣w contains even number of a’s and b’s}.

Ans. For even length string of a and b, the start state of FA is final state, so for zero (i.e., even) length it is accepted, and every additional two a and two b, the FA will make four transitions (three to q_{1},q_{2},q_{3}and fourth back to q_{0}). - For x,y ∈ Σ
^{*}, prove that for any DFA δ(q,xy) = δ(δ(q,x),y), where δ is transition function.

Ans. Solution discussed in the lecture.

- Design a finite automaton for controller for a swing door with a front pad and rear pad. There are two states corresponding to door on and closed, and four possible inputs: front, rear, neither, and both. Ans.: