Formal language & automata theory - End Semester Examination - 2022

2022•Semester 2•Civil-CA•End Semester
Bihar Engineering University, Patna
End Semester Examination - 2022

Formal language & 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 option of the following (Any seven question only):[14]

  1. The language \( \{a^m b^n c^{m+n} / m, n \ge 1\} \) is

    1. regular
    2. context-free but not regular
    3. Context-sensitive but not context free
    4. type-0 but not context sensitive

  2. Which of the following pairs have DIFFERENT expressive powers?

    1. Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)
    2. Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
    3. Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine
    4. Single-tape Turing machine and multi-tape Turing machine

  3. The logic of pumping lemma is a good example of

    1. pigeon-hole principle
    2. divide-and-conquer technique
    3. recursion
    4. iteration

  4. If \( L_1 \) and \( L_2 \) are context free languages, \( L_1 - L_2 \) is

    1. always context-free.
    2. sometimes
    3. never
    4. None of these

  5. _____ is the acyclic graphical representation of a grammer.

    1. Binary tree
    2. Octtree
    3. Parse tree
    4. None of the above

  6. Which of the following pairs of regular expressions are equivalent?

    1. \( x^* \) and \( x^*x \)
    2. \( 1(01) \) and \( (10)^*1 \)
    3. \( x(xx)^* \) and \( (xx)^*x \)
    4. All of the above

  7. The maximum number of states of a DFA converted from an NFA with \( n \) states is

    1. \( n \)
    2. \( n^2 \)
    3. \( 2^n \)
    4. None of these

  8. Definition of a language L with alphabet {a} is given as \( L = \{a^{nk} / 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. \( 2n + 1 \)
    4. \( 2k + 1 \)

  9. 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

  10. Let N be an NFA with \( n \) states and let M be the minimized DFA with \( m \) states recognizing the same language. Which of the following is necessarily true?

    1. \( m \le 2^n \)
    2. \( n \le m \)
    3. M has one accept state
    4. \( m = 2^n \)
Q.2 Solve both questions :[14]

  1. Tabulate Chomsky hierarchy of grammars with an example for each.

  2. Construct the regular grammar accepting the following language: \( L = \{w \in \{a,b\}^* / w \text{ is a string over } \{a, b\} \text{ such that the number of b's is } 3 \mod 4\} \)

Q.3 Solve both questions :[14]

  1. Minimize the DFA.

    Question Diagram

  2. Define recursively enumerable languages. Let \( L_1 \) be recursive and \( L_2 \) recursively enumerable. Show that \( L_2 - L_1 \) is necessarily recursively enumerable.

Q.4 Solve this question :[14]

  1. Begin with the grammar: \( S \rightarrow ASB/\epsilon \), \( A \rightarrow aAS/a \), \( B \rightarrow SbS/A/bb \)
    (i) Eliminate \( \epsilon \)-productions.
    (ii) Eliminate unit productions in the resulting grammar.
    (iii) Eliminate any useless symbol in the resulting grammar.
    (iv) Put the resulting grammar into CNF.

Q.5 Solve both questions :[14]

  1. Design a pushdown automata to accept the following language by empty stack: \( \{0^n 1^n / n \ge 1\} \).

  2. Define deterministic pushdown automata. Explain with an example.

Q.6 Solve both questions :[14]

  1. Prove using pumping lemma for regular languages that the language \( \{0^n / n \text{ is a perfect square}\} \) is not regular.

  2. Convert the following DFA to regular expression using the state elimination technique.

    State / input 0 1
    → *p s p
    q p s
    r r q
    s q r
Q.7 Solve both questions :[14]

  1. Convert the following NFA to DFA and informally describe the language it accepts.

    State / input 0 1
    p {p, q} {p}
    q {r, s} {t}
    r {p, r} {t}
    s ∅ ∅
    *t ∅ ∅

  2. When a CFG is called ambiguous? Show that \( S \rightarrow aS / aSbS / \epsilon \) is ambiguous.

Q.8 Solve both questions :[14]

  1. Define Turing machine. Design a Turing machine M to recognize the language \( \{1^n 2^n 3^n / n \ge 1\} \).

  2. Construct DFA equivalent to the regular expression: \( (0+1)^*(00+11)(0+1)^* \)

Q.9 Write short notes on any two of the following:[14]
    • Pumping lemma for CFL
    • GNF
    • Multistack Turing Machine
    • NP-hard problem