2020 question paper

Formal Language & Automata Theory

27 questions

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

   Module 1: Introduction, Regular languages and finite automata

   Definition of a language $L$ with alphabet $\{a\}$ is given as

   $$L = \{a^{nk} \mid k > 0, \text{ and } n \text{ is a positive integer constant}\}$$

   What is the minimum number of states needed in a DFA to recognize $L$?
   (i) $k + 1$
   (ii) $n + 1$
   (iii) $2^{n + 1}$
   (iv) $2^{k + 1}$

   View this question on its own page →

   CopySearch GoogleAsk AI
2. Q1b. Which of the following versions of Unix came up with YACC first? (i) V3 (ii) V5 (iii) CB UNIX (iv) UNIX-RT20202m

   Module 2: Context-free languages and pushdown automata

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

   (i) V3
   (ii) V5
   (iii) CB UNIX
   (iv) UNIX-RT

   View this question on its own page →

   CopySearch GoogleAsk AI
3. Q1c. A pushdown automata can be represented as \text{PDA} = \epsilon\text{-NFA} + [\text{stack}]. (i) True (ii) False20202m

   Module 2: Context-free languages and pushdown automata

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

   (i) True
   (ii) False

   View this question on its own page →

   CopySearch GoogleAsk AI
4. Q1d. 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 above20202m

   Module 2: Context-free languages and pushdown automata

   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 →

   CopySearch GoogleAsk AI
5. Q1e. A _____ is context free grammar with atmost one non-terminal in the right handside of the production. (i) linear grammar (ii) linear bounded grammar (iii) regular grammar (iv) None of the above20202m

   Module 1: Introduction, Regular languages and finite automata

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

   (i) linear grammar
   (ii) linear bounded grammar
   (iii) regular grammar
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1f. 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? (i) Finite state automata (ii) Deterministic pushdown automata (iii) Non-deterministic pushdown automata (iv) Turing machine20202m

   Module 1: Introduction, Regular languages and finite automata

   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?

   (i) Finite state automata
   (ii) Deterministic pushdown automata
   (iii) Non-deterministic pushdown automata
   (iv) Turing machine

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1g. Let L = \{w \mid w \in \{0+1\}^*, w \text{ has even number of 1s}\}. Which one of the regular expression below represents L? (i) (0^* 10^* 1)^* (ii) 0^*(10^* 10^*)^* (iii) 0^* (10^* 1^*)^* 0^* (iv) 0^* 1(10^* 1)^* 10^*20202m

   Module 1: Introduction, Regular languages and finite automata

   Let $L = \{w \mid w \in \{0+1\}^*, w \text{ has even number of 1s}\}$. Which one of the regular expression below represents $L$?

   (i) $(0^* 10^* 1)^*$
   (ii) $0^*(10^* 10^*)^*$
   (iii) $0^* (10^* 1^*)^* 0^*$
   (iv) $0^* 1(10^* 1)^* 10^*$

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q1h. 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\}? (i) Ten (ii) Nine (iii) Eight (iv) Six20202m

   Module 1: Introduction, Regular languages and finite automata

   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\}$?

   (i) Ten
   (ii) Nine
   (iii) Eight
   (iv) Six

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q1i. The decision problem is the function from string to _____. (i) char (ii) int (iii) boolean (iv) None of the above20202m

   Module 5: Undecidability

   The decision problem is the function from string to _____.

   (i) char
   (ii) int
   (iii) boolean
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q1j. A language L may not be accepted by a turing machine if (i) it is recursively enumerable (ii) it is recursive (iii) L can be enumerated by some turing machine (iv) None of the above20202m

    Module 4: Turing machines

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

    (i) it is recursively enumerable
    (ii) it is recursive
    (iii) $L$ can be enumerated by some turing machine
    (iv) None of the above

    View this question on its own page →

    CopySearch GoogleAsk AI
12. Q2a. Write the context-free grammar to create palindrome over \{a, b\}.20207m

    Module 2: Context-free languages and pushdown automata

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

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q2b. 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.20207m

    Module 1: Introduction, Regular languages and finite automata

    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.

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q3a. Design a turing machine to compute the sum of two positive integers m and n.20207m

    Module 4: Turing machines

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

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q3b. Design ANPDA for accepting the string L = \{\text{set of all palindrome over } \{a, b\}\} by the empty stack and by final state.20207m

    Module 2: Context-free languages and pushdown automata

    Design ANPDA for accepting the string $L = \{\text{set of all palindrome over } \{a, b\}\}$ by the empty stack and by final state.

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Construct finite automaton corresponding to the regular expression: (a+b)^* c d^* e20207m

    Module 1: Introduction, Regular languages and finite automata

    Construct finite automaton corresponding to the regular expression:

    $$(a+b)^* c d^* e$$

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Explain the multi-tape version of turing machine and its significance.20207m

    Module 4: Turing machines

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

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. Show given grammar over alphabet \{a, b\} verify whether it is ambiguous or unambiguous: S \to a \mid abSb \mid aAb A \to bS \mid aAAb20207m

    Module 2: Context-free languages and pushdown automata

    Show given grammar over alphabet $\{a, b\}$ verify whether it is ambiguous or unambiguous:

    $$S \to a \mid abSb \mid aAb$$
    $$A \to bS \mid aAAb$$

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q6a. Prove that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.20207m

    Module 2: Context-free languages and pushdown automata

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

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6b. Design a pushdown automaton for the following context-free grammar: S \to aB \mid bA A \to aS \mid bAA \mid a B \to bS \mid aBB \mid b20207m

    Module 2: Context-free languages and pushdown automata

    Design a pushdown automaton for the following context-free grammar:

    $$S \to aB \mid bA$$
    $$A \to aS \mid bAA \mid a$$
    $$B \to bS \mid aBB \mid b$$

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q7a. Design a turing machine that accepts all palindromes over \Sigma = \{a, b\}.20207m

    Module 4: Turing machines

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

    View this question on its own page →

    CopySearch GoogleAsk AI
23. Q7b. Explain Myhill-Nerode theorem for minimization of automata with suitable example.20207m

    Module 1: Introduction, Regular languages and finite automata

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

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q8a. 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.20207m

    Module 4: Turing machines

    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.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8b. 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.20207m

    Module 2: Context-free languages and pushdown automata

    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.

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q9a. Write a short note on: Minimization of automata20203.5m

    Module 1: Introduction, Regular languages and finite automata

    Write a short note on: Minimization of automata

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9b. Write a short note on: Type 2 grammar (context free)20203.5m

    Module 2: Context-free languages and pushdown automata

    Write a short note on: Type 2 grammar (context free)

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9c. Write a short note on: NP-hard problem20203.5m

    Module 5: Undecidability

    Write a short note on: NP-hard problem

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9d. Write a short note on: Pumping lemma for CFL20203.5m

    Module 2: Context-free languages and pushdown automata

    Write a short note on: Pumping lemma for CFL

    View this question on its own page →

    CopySearch GoogleAsk AI