[Total No. of Questions - 8]
[Total No. of Printed Pages - 2]


B.E. vth Semester Examination
BE-V/6(B)
216351
Computer Engineering
Course No. COM-504
Automata and Formal Languages
New Syllabus
Time Allowed - 3 Hours Maximum Marks - 100

Note: Attempt any five questions selecting at least two questions from each section. All questions carry equal            marks.

Section - A

    1. Prove that if r is a regular expression, then there exists a NFA with E-transitions that accepts L(r).
    2. What are the applications of finite automata?
    1. Construct a non deterministic finite automata accepting the set of all strings over {a,b} ending in aba. Use it to construct a DFA accepting the same set of strings.
    2. Define a regular expression. Whar are its properties?
    1. Construct a minimum state automata equivalent to the following transition diagram:
    2. Prove that for any transition function d(del)and for any two input strings x and y:
           d(q,xy) = d(d(q,x)y)     [here d denotes del]
    1. What is pumping lemma. What are its applications?
    2. Construct a finite automata for accepting all possible strings of zero's and one's which does not contain 001 as substring.
    3. Construct a mealy machine which is equivalent to the following moore machine:

      4. Present StateNext StateOutput
      a = 0a = 1
       —> q0q1q21
      q1q3q20
      q2q2q11
      q3q0q31

Section - B

    1. Write a short note on acceptors and generators.
    2. Explain different types of turing machines.
    1. Reduce the following grammer to CNF:
           S —> abSb | a | aAb,   A —> bS | aAAb
    2. Explain Greibach Normal Form with a suitable example.
    1. What is ambiguity. Differentiate between leftmost and rightmost derivation trees.
    2. What do you mean by useless symbols.
    1. Construct a pushdown automata acceptin:
           { an  b2n / n > 1 }
    2. Explain the halting problem of turing machines.





    5. ********************