PyQdeck LogoPyQdeckSubjects

2023 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

28 questions

  1. Q1a. A language accepted by deterministic pushdown automata is closed under which of the following? (i) Complement (ii) Union (iii) Both (i) and (ii) (iv) None of the above20232m

    Module 2: Context-Free Languages (CFL) and PDA

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

    (i) Complement
    (ii) Union
    (iii) Both (i) and (ii)
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  2. Q1b. 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? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n20232m

    Module 1: Introduction & Regular Languages

    Let NN be an NFA with nn states and let MM be the minimized DFA with mm states recognizing the same language. Which of the following is necessarily true?

    (i) m≤2nm \le 2^n
    (ii) n≤mn \le m
    (iii) MM has one accept state
    (iv) m=2nm = 2^n

    View this question on its own page →
    Search GoogleAsk AI
  3. Q1c. A minimum state deterministic FA accepting the language: L = \{ w \mid w \in \{0,1\}^* \} where the number of 0's and 1's in w are divisible by 3 and 5 respectively, has: (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20232m

    Module 1: Introduction & Regular Languages

    A minimum state deterministic FA accepting the language:

    L={w∣w∈{0,1}∗}L = \{ w \mid w \in \{0,1\}^* \}

    where the number of 0's and 1's in ww are divisible by 3 and 5 respectively, has:

    (i) 15 states
    (ii) 11 states
    (iii) 10 states
    (iv) 9 states

    View this question on its own page →
    Search GoogleAsk AI
  4. Q1d. The language \{ a^n b^n c^{n+m} \mid m, n \ge 1 \} is: (i) regular (ii) context-free but not regular (iii) context-sensitive but not context-free (iv) type 0 but not context-sensitive20232m

    Module 3: Context-Sensitive Languages

    The language {anbncn+m∣m,n≥1}\{ a^n b^n c^{n+m} \mid m, n \ge 1 \} is:

    (i) regular
    (ii) context-free but not regular
    (iii) context-sensitive but not context-free
    (iv) type 0 but not context-sensitive

    View this question on its own page →
    Search GoogleAsk AI
  5. Q1e. The string 1101 does not belong to the set represented by: (i) 1^* 0^* (0+1) (ii) 1(0+1)^*101 (iii) (1(0)^*(0+1)^*(0+1))^* (iv) \{00 + (11)^*0\}^*20232m

    Module 1: Introduction & Regular Languages

    The string 11011101 does not belong to the set represented by:

    (i) 1∗0∗(0+1)1^* 0^* (0+1)
    (ii) 1(0+1)∗1011(0+1)^*101
    (iii) (1(0)∗(0+1)∗(0+1))∗(1(0)^*(0+1)^*(0+1))^*
    (iv) {00+(11)∗0}∗\{00 + (11)^*0\}^*

    View this question on its own page →
    Search GoogleAsk AI
  6. Q1f. A given grammar is called ambiguous if: (i) two or more productions have the same non-terminal on LHS (ii) a derivation tree has more than one associated sentence (iii) there exists a sentence with more than one derivation tree (iv) brackets are not present in the grammar20232m

    Module 2: Context-Free Languages (CFL) and PDA

    A given grammar is called ambiguous if:

    (i) two or more productions have the same non-terminal on LHS
    (ii) a derivation tree has more than one associated sentence
    (iii) there exists a sentence with more than one derivation tree
    (iv) brackets are not present in the grammar

    View this question on its own page →
    Search GoogleAsk AI
  7. Q1g. Which one of the following statements is true? (i) The intersection of two CFLs is context-free (ii) Every CFL can be accepted by a DPDA (iii) The union of two CFLs is context-free (iv) The complement of a CFL is context-free20232m

    Module 2: Context-Free Languages (CFL) and PDA

    Which one of the following statements is true?

    (i) The intersection of two CFLs is context-free
    (ii) Every CFL can be accepted by a DPDA
    (iii) The union of two CFLs is context-free
    (iv) The complement of a CFL is context-free

    View this question on its own page →
    Search GoogleAsk AI
  8. Q1h. From the options, the pair having different expressive powers is: (i) DPDA and NPDA (ii) DFA and NFA (iii) single-tape TM and multi-tape TM (iv) deterministic single-tape TM and nondeterministic single-tape TM20232m

    Module 4: Turing Machines (TM)

    From the options, the pair having different expressive powers is:

    (i) DPDA and NPDA
    (ii) DFA and NFA
    (iii) single-tape TM and multi-tape TM
    (iv) deterministic single-tape TM and nondeterministic single-tape TM

    View this question on its own page →
    Search GoogleAsk AI
  9. Q1i. Recursive languages are: (i) a proper superset of CFLs (ii) always recognizable (iii) also called type-0 languages (iv) recognizable by Turing machines20232m

    Module 4: Turing Machines (TM)

    Recursive languages are:

    (i) a proper superset of CFLs
    (ii) always recognizable
    (iii) also called type-0 languages
    (iv) recognizable by Turing machines

    View this question on its own page →
    Search GoogleAsk AI
  10. Q1j. If P and Q are regular expressions (P is not null), then R = Q + RP has the unique solution: (i) R = QP (ii) R = PQ^* (iii) R = QP^* (iv) R = QP^*20232m

    Module 1: Introduction & Regular Languages

    If PP and QQ are regular expressions (PP is not null), then R=Q+RPR = Q + RP has the unique solution:

    (i) R=QPR = QP
    (ii) R=PQ∗R = PQ^*
    (iii) R=QP∗R = QP^*
    (iv) R=QP∗R = QP^*

    View this question on its own page →
    Search GoogleAsk AI
  12. Q2a. Discuss the Chomsky hierarchy of grammars with suitable examples.20237m

    Module 1: Introduction & Regular Languages

    Discuss the Chomsky hierarchy of grammars with suitable examples.

    View this question on its own page →
    Search GoogleAsk AI
  13. Q2b. State the pumping lemma for context-free languages.20237m

    Module 2: Context-Free Languages (CFL) and PDA

    State the pumping lemma for context-free languages.

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3a. Design a PDA (empty stack and final state both) for L = \{ WW^r \mid W \in \{a,b\}^* \}.20237m

    Module 2: Context-Free Languages (CFL) and PDA

    Design a PDA (empty stack and final state both) for L={WWr∣W∈{a,b}∗}L = \{ WW^r \mid W \in \{a,b\}^* \}.

    View this question on its own page →
    Search GoogleAsk AI
  15. Q3b. Eliminate \varepsilon, unit, and useless productions from the grammar: A → bA | Bba | aa B → aba | b | D C → CA | AC | B D → a | \varepsilon20237m

    Module 2: Context-Free Languages (CFL) and PDA

    Eliminate ε\varepsilon, unit, and useless productions from the grammar:

    A → bA | Bba | aa
    B → aba | b | D
    C → CA | AC | B
    D → a | ε\varepsilon

    View this question on its own page →
    Search GoogleAsk AI
  16. Q4a. Define Chomsky Normal Form. Convert the CFG: S → aSb | ab | Aa A → aab to CNF.20237m

    Module 2: Context-Free Languages (CFL) and PDA

    Define Chomsky Normal Form. Convert the CFG:

    S → aSb | ab | Aa
    A → aab

    to CNF.

    View this question on its own page →
    Search GoogleAsk AI
  17. Q4b. Obtain the regular expression for the given DFA. ![image](https://res.cloudinary.com/djkpavwmp/image/upload/v1766231140/portfolio_assets/fbcklkz4il80phefuvuo.png)20237m

    Module 1: Introduction & Regular Languages

    Obtain the regular expression for the given DFA.

    image

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5a. Prove that if L_1 and L_2 are regular, then L_1 \cup L_2 is regular.20237m

    Module 1: Introduction & Regular Languages

    Prove that if L1L_1 and L2L_2 are regular, then L1∪L2L_1 \cup L_2 is regular.

    View this question on its own page →
    Search GoogleAsk AI
  19. Q5b. Design a Turing machine that recognizes strings containing equal number of 0’s and 1’s.20237m

    Module 4: Turing Machines (TM)

    Design a Turing machine that recognizes strings containing equal number of 00’s and 11’s.

    View this question on its own page →
    Search GoogleAsk AI
  20. Q6a. Given the \varepsilon-NFA, compute \varepsilon-closures and convert to DFA. | State | \varepsilon-transition | a-transition | b-transition | |-------|--------------------------|--------------|--------------| | → | {r} | {q} | {p,r} | | q | ∅ | {p} | ∅ | | r | {p,q} | {r} | {p} |20237m

    Module 1: Introduction & Regular Languages

    Given the ε\varepsilon-NFA, compute ε\varepsilon-closures and convert to DFA.

    State ε\varepsilon-transition a-transition b-transition
    → {r} {q} {p,r}
    q ∅ {p} ∅
    r {p,q} {r} {p}
    View this question on its own page →
    Search GoogleAsk AI
  21. Q6b. Construct NFA for the regular expression: (0+1)^*00(0+1)^*20237m

    Module 1: Introduction & Regular Languages

    Construct NFA for the regular expression:

    (0+1)∗00(0+1)∗ (0+1)^*00(0+1)^*

    View this question on its own page →
    Search GoogleAsk AI
  23. Q7a. Construct NPDA for the grammar: S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A20237m

    Module 2: Context-Free Languages (CFL) and PDA

    Construct NPDA for the grammar:

    S→αABB∣αAAA→αBB∣αB→bBB∣A S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A

    View this question on its own page →
    Search GoogleAsk AI
  24. Q7b. Prove the identity: (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) = 0^*1(0+10^*1)^*20237m

    Module 1: Introduction & Regular Languages

    Prove the identity:

    (1+00∗1)+(1+00∗1)(0+10∗1)∗(0+10∗1)=0∗1(0+10∗1)∗ (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) = 0^*1(0+10^*1)^*

    View this question on its own page →
    Search GoogleAsk AI
  25. Q8a. Construct a Moore machine equivalent to the given Mealy machine.20237m

    Module 1: Introduction & Regular Languages

    Construct a Moore machine equivalent to the given Mealy machine.

    View this question on its own page →
    Search GoogleAsk AI
  26. Q8b. Given the grammar: S \to aB \mid ba \\ B \to b \mid bs \mid aBB For the string aaabbabbba find: 1. Leftmost derivation 2. Rightmost derivation 3. Parse tree20237m

    Module 2: Context-Free Languages (CFL) and PDA

    Given the grammar:

    S→aB∣baB→b∣bs∣aBB S \to aB \mid ba \\ B \to b \mid bs \mid aBB

    For the string aaabbabbbaaaabbabbba find:

    1. Leftmost derivation
    2. Rightmost derivation
    3. Parse tree
    View this question on its own page →
    Search GoogleAsk AI
  27. Q9a. Write short notes on: Post Correspondence Problem.20237m

    Module 5: Undecidability

    Write short notes on: Post Correspondence Problem.

    View this question on its own page →
    Search GoogleAsk AI
  28. Q9b. Write short notes on: Multi-tape Turing Machine.20237m

    Module 4: Turing Machines (TM)

    Write short notes on: Multi-tape Turing Machine.

    View this question on its own page →
    Search GoogleAsk AI
  29. Q9c. Write short notes on: NP-hard and NP-complete problems.20237m

    Module 5: Undecidability

    Write short notes on: NP-hard and NP-complete problems.

    View this question on its own page →
    Search GoogleAsk AI
  30. Q9d. Write short notes on: Pumping lemma for CFL.20237m

    Module 2: Context-Free Languages (CFL) and PDA

    Write short notes on: Pumping lemma for CFL.

    View this question on its own page →
    Search GoogleAsk AI
Previous year2022Next year2024