FORMAL LANGUAGES AND AUTOMATA THEORY - B.Tech 5th Semester Exam., 2020

2020•Semester 2•Civil-CA•End Semester
Bihar Engineering University, Patna
B.Tech 5th Semester Exam., 2020

FORMAL LANGUAGES AND AUTOMATA THEORY

Time: 03 HoursCode: 105503Full Marks: 70

Instructions:

  1. The marks are indicated in the right-hand margin.
  2. There are NINE questions in this paper.
  3. Attempt FIVE questions in all.
  4. Question No. 1 is compulsory.
Q.1 Choose the correct answer of the following (any seven):[14]

  1. Definition of a language L with alphabet {a} is given as \( L = \{a^{nk} \mid k > 0 \}, \) and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

    1. \( k + 1 \)
    2. \( n + 1 \)
    3. \( 2^{n+1} \)
    4. \( 2^{k+1} \)

  2. Which of the following versions of Unix came up with YACC first?

    1. V3
    2. V5
    3. CB UNIX
    4. UNIX-RT

  3. A pushdown automata can be represented as \( PDA = \epsilon \text{-} NFA + [\text{stack}] \).

    1. True
    2. False

  4. A language accepted by deterministic pushdown automata is closed under which of the following?

    1. Complement
    2. Union
    3. Both (i) and (ii)
    4. None of the above

  5. A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

    1. linear grammar
    2. linear bounded grammar
    3. regular grammar
    4. None of the above

  6. The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

    1. Finite state automata
    2. Deterministic pushdown automata
    3. Non-deterministic pushdown automata
    4. Turing machine

  7. Let \( L = \{w \in (0+1)^* \mid w \text{ has even number of 1s}\} \), i.e., L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

    1. \( (0^*10^*1)^* \)
    2. \( 0^*(10^*10^*)^* \)
    3. \( 0^*(10^*1^*)^*0^* \)
    4. \( 0^*1(10^*1)^*10^* \)

  8. What is the minimum number of states in deterministic finite automata (DFA) for string starting with \( ba^2 \) and ending with a over alphabet {a, b}?

    1. Ten
    2. Nine
    3. Eight
    4. None of the above

  9. The decision problem is the function from string to

    1. char
    2. int
    3. boolean
    4. None of the above

  10. A language L may not be accepted by a turing machine if

    1. it is recursively enumerable
    2. it is recursive
    3. L can be enumerated by some turing machine
    4. None of the above
Q.2 Solve both questions :[14]

  1. Write the context-free grammar to create palindrome over {a, b}.

  2. Construct a DFA which accepts the set of all binary strings that interpreted as binary representation of an unsigned decimal integer, is divisible by 5.

Q.3 Solve both questions :[14]

  1. Design a turing machine to compute the sum of two positive integers m and n.

  2. Design a NPDA for accepting the string \( L = \) set of all palindrome over {a, b} by the empty stack and by final state.

Q.4 Solve both questions :[14]

  1. Construct finite automaton corresponding to the regular expression: \( (a+b)^*c d^*e \)

  2. Explain the multi-tape version of turing machine and its significance.

Q.5 Solve both questions :[14]

  1. Show given grammar over alphabet {a, b} verify whether it is ambiguous or unambiguous : \( S \rightarrow a / abSb / aAb \), \( A \rightarrow bS / aAAb \)

  2. Show that \( L = \) palindrome over {a, b} is not regular.

Q.6 Solve both questions :[14]

  1. Prove that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.

  2. Design a pushdown automaton for the following context-free grammar: \( S \rightarrow aB \mid bA \), \( A \rightarrow aS \mid bAA \mid a \), \( B \rightarrow bS \mid aBB \mid b \)

Q.7 Solve both questions :[14]

  1. Design a turing machine that accepts all palindromes over \( \Sigma = \{a, b\} \).

  2. Explain Myhill-Nerode theorem for minimization of automata with suitable example.

Q.8 Solve both questions :[14]

  1. Prove that if L is the language generated by an unrestricted grammar \( G=(N,T,P,S) \), then L is recognized by a turing machine.

  2. Design a pushdown automata for accepting the string for the language \( L = \{WW^R \mid W \in (a,b)^*\} \) by the empty stack as well as final state.

Q.9 Write short notes on the following:[14]
    • Minimization of automata
    • Type 2 grammar (Context free)
    • NP-hard problem
    • Pumping lemma for CFL