Theory of Computation, Assignment # 1 Solution Hints
B.tech. IV Sem (CSE), 2018-19


February 10, 2019
  1. 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.
  2. 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, ....
  3. 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.
  4. 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.)
  5. 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.
  6. 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) {ww ∈{a,b}* and every run of a has even length}.
    {ww ∈{a,b}* and number of as and bs are even in w}.
  7. 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.)
  8. 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.
  9. 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 q1,q2,q3 and fourth back to q0).
  10. For x,y Σ*, prove that for any DFA δ(q,xy) = δ(δ(q,x),y), where δ is transition function.
    Ans. Solution discussed in the lecture.
  11. 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.: PIC