PyQdeck LogoPyQdeckSubjects

2019 question paper

Formal Language & Automata Theory

23 questions

  1. Q1a. Consider the following finite state automaton: ![diagram](https://res.cloudinary.com/djkpavwmp/image/upload/v1772535007/portfolio_assets/pqw1kjcbjvg9smtpnu3w.png) The language accepted by this automaton is given by the regular expression (i) b^*ab^*ab^*ab (ii) (a+b)^* (iii) b^*a(a+b)^* (iv) b^*ab^*ab20192m

    Module 1: Introduction, Regular languages and finite automata

    Consider the following finite state automaton:

    diagram

    The language accepted by this automaton is given by the regular expression
    (i) b∗ab∗ab∗abb^*ab^*ab^*ab
    (ii) (a+b)∗(a+b)^*
    (iii) b∗a(a+b)∗b^*a(a+b)^*
    (iv) b∗ab∗abb^*ab^*ab

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

    Module 1: Introduction, Regular languages and finite automata

    A minimum state deterministic finite automaton accepting the language

    L={w∣w∈{0,1}∗, number of 0’s and 1’s in w are divisible by 3 and 5 respectively}L = \{w \mid w \in \{0, 1\}^*, \text{ number of 0's and 1's in } w \text{ 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
  3. Q1d. Consider the following languages: GATE[2005] L_1 = \{ww^R \mid w \in \{0, 1\}^*\} L_2 = \{w\#w^R \mid w \in \{0, 1\}^*\} where \# is a special symbol, L_3 = \{ww \mid w \in \{0, 1\}^*\} Which one of the following is true? (i) L_1 is a deterministic CFL (ii) L_2 is a deterministic CFL (iii) L_3 is a CFL, but not a deterministic CFL (iv) L_3 is a deterministic CFL20192m

    Module 2: Context-free languages and pushdown automata

    Consider the following languages:
    GATE[2005]
    L1={wwR∣w∈{0,1}∗}L_1 = \{ww^R \mid w \in \{0, 1\}^*\}
    L2={w#wR∣w∈{0,1}∗}L_2 = \{w\#w^R \mid w \in \{0, 1\}^*\}
    where #\# is a special symbol,
    L3={ww∣w∈{0,1}∗}L_3 = \{ww \mid w \in \{0, 1\}^*\}

    Which one of the following is true?
    (i) L1L_1 is a deterministic CFL
    (ii) L2L_2 is a deterministic CFL
    (iii) L3L_3 is a CFL, but not a deterministic CFL
    (iv) L3L_3 is a deterministic CFL

    View this question on its own page →
    Search GoogleAsk AI
  4. Q1e. Consider the following statements about the context-free grammar: (1) G = \{S \to SS, S \to ab, S \to ba, S \to \epsilon\} (2) G is ambiguous (3) G produces all strings with equal number of a's and b's G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G? (i) 1 only (ii) 1 and 3 (iii) 2 and 3 (iv) 1, 2 and 320192m

    Module 2: Context-free languages and pushdown automata

    Consider the following statements about the context-free grammar:
    (1) G={S→SS,S→ab,S→ba,S→ϵ}G = \{S \to SS, S \to ab, S \to ba, S \to \epsilon\}
    (2) GG is ambiguous
    (3) GG produces all strings with equal number of aa's and bb's

    GG can be accepted by a deterministic PDA. Which combination below expresses all the true statements about GG?
    (i) 1 only
    (ii) 1 and 3
    (iii) 2 and 3
    (iv) 1, 2 and 3

    View this question on its own page →
    Search GoogleAsk AI
  5. Q1f. Consider the grammar G whose SLR parser has n_1 states and LALR parser has n_2 states. What is the relation between n_1 and n_2? (i) n_1 = n_2 (ii) n_1 < n_2 (iii) n_1 > n_2 (iv) None of the above20192m

    Module 2: Context-free languages and pushdown automata

    Consider the grammar GG whose SLR parser has n1n_1 states and LALR parser has n2n_2 states. What is the relation between n1n_1 and n2n_2?

    (i) n1=n2n_1 = n_2
    (ii) n1<n2n_1 < n_2
    (iii) n1>n2n_1 > n_2
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  6. Q1g. Let w be any string of length n in \{0, 1\}^*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic FA that accepts L? (i) n - 1 (ii) n (iii) n + 1 (iv) 2n - 120192m

    Module 1: Introduction, Regular languages and finite automata

    Let ww be any string of length nn in {0,1}∗\{0, 1\}^*. Let LL be the set of all substrings of ww. What is the minimum number of states in a non-deterministic FA that accepts LL?

    (i) n−1n - 1
    (ii) nn
    (iii) n+1n + 1
    (iv) 2n−12n - 1

    View this question on its own page →
    Search GoogleAsk AI
  7. Q1h. Consider the regular expression (0+1)(0+1)\dots N \text{ times}. The minimum state FA that recognizes the language represented by this regular expression contains (i) n states (ii) (n+1) states (iii) (n+2) states (iv) None of the above20192m

    Module 1: Introduction, Regular languages and finite automata

    Consider the regular expression (0+1)(0+1)…N times(0+1)(0+1)\dots N \text{ times}. The minimum state FA that recognizes the language represented by this regular expression contains

    (i) nn states
    (ii) (n+1)(n+1) states
    (iii) (n+2)(n+2) states
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  8. Q1i. In Mealy machine, output is a function of (i) present state only (ii) next state only (iii) present state and input (iv) input only20192m

    Module 1: Introduction, Regular languages and finite automata

    In Mealy machine, output is a function of

    (i) present state only
    (ii) next state only
    (iii) present state and input
    (iv) input only

    View this question on its own page →
    Search GoogleAsk AI
  9. Q1j. 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 = 2n20192m

    Module 1: Introduction, Regular languages and finite automata

    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 = 2n

    View this question on its own page →
    Search GoogleAsk AI
  10. Q2a. Design deterministic finite automata for the set of strings over the alphabet \{a, b\} containing at least three occurrences of three consecutive b's, overlapping permitted (e.g., the string bbbbb should be accepted).20197m

    Module 1: Introduction, Regular languages and finite automata

    Design deterministic finite automata for the set of strings over the alphabet {a,b}\{a, b\} containing at least three occurrences of three consecutive bb's, overlapping permitted (e.g., the string bbbbbbbbbb should be accepted).

    View this question on its own page →
    Search GoogleAsk AI
  12. Q2b. Let \Sigma = \{0, 1\}. Let L be the language that consists of strings having either 01 repeated one or more times or 010 repeated one or more times. Is L regular? Explain.20197m

    Module 1: Introduction, Regular languages and finite automata

    Let Σ={0,1}\Sigma = \{0, 1\}. Let LL be the language that consists of strings having either 0101 repeated one or more times or 010010 repeated one or more times. Is LL regular? Explain.

    View this question on its own page →
    Search GoogleAsk AI
  13. Q3a. Assume that a regular language L is provided to you as a DFA M(\{Q, \Sigma, \delta, q_0, F\}). How would you check whether L is infinite?20197m

    Module 1: Introduction, Regular languages and finite automata

    Assume that a regular language LL is provided to you as a DFA M({Q,Σ,δ,q0,F})M(\{Q, \Sigma, \delta, q_0, F\}). How would you check whether LL is infinite?

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3b. Design a push-down 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.20197m

    Module 2: Context-free languages and pushdown automata

    Design a push-down automata for accepting the string for the language L={WWR∣W∈{a,b}∗}L = \{WW^R \mid W \in \{a, b\}^*\} by the empty stack as well as final state.

    View this question on its own page →
    Search GoogleAsk AI
  15. Q4a. Construct a Moore machine which determines the residue mod 3 for each binary string treated as binary integer. And then convert into the corresponding Mealy machine.20197m

    Module 1: Introduction, Regular languages and finite automata

    Construct a Moore machine which determines the residue mod 3 for each binary string treated as binary integer. And then convert into the corresponding Mealy machine.

    View this question on its own page →
    Search GoogleAsk AI
  16. Q4b. Design finite state machine or abstract model for binary adder.20197m

    Module 1: Introduction, Regular languages and finite automata

    Design finite state machine or abstract model for binary adder.

    View this question on its own page →
    Search GoogleAsk AI
  17. Q5a. Prove that the language L = \{a^{i^2} \mid i \ge 1\} is not context-free language.20197m

    Module 2: Context-free languages and pushdown automata

    Prove that the language L={ai2∣i≥1}L = \{a^{i^2} \mid i \ge 1\} is not context-free language.

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5b. Show that L = \text{palindrome over } \{a, b\} is not regular.20197m

    Module 1: Introduction, Regular languages and finite automata

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

    View this question on its own page →
    Search GoogleAsk AI
  19. Q6a. Consider the following language: L = \{a^m b^{2n} c^{3n} d^p \mid p > m \text{ and } m, n \ge 1\} Write a context-free grammar to generate L and write shortest string in L.20197m

    Module 2: Context-free languages and pushdown automata

    Consider the following language:
    L={amb2nc3ndp∣p>m and m,n≥1}L = \{a^m b^{2n} c^{3n} d^p \mid p > m \text{ and } m, n \ge 1\}

    Write a context-free grammar to generate LL and write shortest string in LL.

    View this question on its own page →
    Search GoogleAsk AI
  20. Q6b. Convert the following context-free grammar into GNF: S \to XY X \to YS \mid b Y \to SX \mid a20197m

    Module 2: Context-free languages and pushdown automata

    Convert the following context-free grammar into GNF:
    S→XYS \to XY
    X→YS∣bX \to YS \mid b
    Y→SX∣aY \to SX \mid a

    View this question on its own page →
    Search GoogleAsk AI
  21. Q7a. Construct a push-down automata that accepts the following language: L = \{uawb \mid u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}20197m

    Module 2: Context-free languages and pushdown automata

    Construct a push-down automata that accepts the following language:
    L={uawb∣u and w∈{a,b}∗ and ∣u∣=∣w∣}L = \{uawb \mid u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}

    View this question on its own page →
    Search GoogleAsk AI
  23. Q7b. Using the following grammar S \to AB \mid BC A \to BA \mid a B \to CC \mid b C \to AB \mid a use the CYK algorithm to determine whether the given string baaba is in L(G) or not.20197m

    Module 2: Context-free languages and pushdown automata

    Using the following grammar
    S→AB∣BCS \to AB \mid BC
    A→BA∣aA \to BA \mid a
    B→CC∣bB \to CC \mid b
    C→AB∣aC \to AB \mid a

    use the CYK algorithm to determine whether the given string baababaaba is in L(G)L(G) or not.

    View this question on its own page →
    Search GoogleAsk AI
  24. Q8a. Design a Turing machine to perform 2's compliment operation on binary string.20197m

    Module 4: Turing machines

    Design a Turing machine to perform 2's compliment operation on binary string.

    View this question on its own page →
    Search GoogleAsk AI
  25. Q8b. Write short notes on the following: (i) Deterministic PDA vs. non-deterministic PDA (ii) Universal Turing machine (iii) Non-deterministic Turing machine (iv) Post correspondence problem (PCP)20197m

    Module 5: Undecidability

    Write short notes on the following:
    (i) Deterministic PDA vs. non-deterministic PDA
    (ii) Universal Turing machine
    (iii) Non-deterministic Turing machine
    (iv) Post correspondence problem (PCP)

    View this question on its own page →
    Search GoogleAsk AI
Next year2020