Theory of computation miscellaneous

Theory of computation miscellaneous

Easy Questions

Theory of Computation

Theory of computation miscellaneous
  1. Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic pushdown automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is true?








  1. View Hint View Answer Discuss in Forum

    We know that, the languages accepted by non deterministic finite automata are also accepted by deterministic finite automata. This may not be in the case of context-free languages.
    Therefore, Df = Nf and Dp ⊂ Np

    Correct Option: D

    We know that, the languages accepted by non deterministic finite automata are also accepted by deterministic finite automata. This may not be in the case of context-free languages.
    Therefore, Df = Nf and Dp ⊂ Np

  1. Consider the following statements about the context-free grammar:
    G = { S → SS, S → ab, S → ba, S → ∈ }
    1. G is ambiguous.
    2. G produces all strings with equal number of a's and b's.
    3. G can be accepted by a deterministic PDA.
    Which combination below expresses all the true statements about G?








  1. View Hint View Answer Discuss in Forum

    Due to S → S this Grammar is ambiguous right hand side has two Non terminals. Also the strings like aaabbb have equal no. of a's & b's but can't be produced by this grammar. So 2 is false.
    Statement 3 is true since it is a CFG so accepted by PDA.

    Correct Option: B

    Due to S → S this Grammar is ambiguous right hand side has two Non terminals. Also the strings like aaabbb have equal no. of a's & b's but can't be produced by this grammar. So 2 is false.
    Statement 3 is true since it is a CFG so accepted by PDA.

  1. Which of the following problems is undecidable?








  1. View Hint View Answer Discuss in Forum

    Finite state automata (FSA) has no undecidability CFL membership problem is also decidable. So option (b) i.e Ambiguity of CFL cannot be decidable.

    Correct Option: B

    Finite state automata (FSA) has no undecidability CFL membership problem is also decidable. So option (b) i.e Ambiguity of CFL cannot be decidable.

  1. Which of the following statements are true?
    1. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa.
    2. All ε-productions can be removed from any context free grammar by suitable transformations.
    3. The language generated by a context-free grammar all of whose productions are of the form X → W or X → WY (where, W is a string of terminals and Y is non terminal), is always regular.
    4. The derivation trees of strings generated by a context free grammar in Chomsky Normal Form are always binary trees.








  1. View Hint View Answer Discuss in Forum

    Statement 1 is true : Using GNF we can convert Left recursive grammar to right recursive and by using reversal of CFG and GNF we can convert right recursive to left recursive.
    Statement 2 is false : because if Î is in the language then we can't remove ∈ production from Start symbol. (For example L = a*)
    Statement 3 is true because right linear grammar generates regular set
    Statement 4 is true, only two non-terminals are there in each production in CNF. So it always form a binary tree.

    Correct Option: C

    Statement 1 is true : Using GNF we can convert Left recursive grammar to right recursive and by using reversal of CFG and GNF we can convert right recursive to left recursive.
    Statement 2 is false : because if Î is in the language then we can't remove ∈ production from Start symbol. (For example L = a*)
    Statement 3 is true because right linear grammar generates regular set
    Statement 4 is true, only two non-terminals are there in each production in CNF. So it always form a binary tree.

  1. Which one of the following is false?








  1. View Hint View Answer Discuss in Forum

    (a) true, since minimal DFA for every regular language is possible.
    (b) true, NFA can be converted into an equivalent PDA.
    (c) CG'S are not recursive but their complements are.
    (d) false, since non deterministic PDA represents, non deterministic. CFG, since NDCFG and CFG are proper subsets so conversion required.

    Correct Option: D

    (a) true, since minimal DFA for every regular language is possible.
    (b) true, NFA can be converted into an equivalent PDA.
    (c) CG'S are not recursive but their complements are.
    (d) false, since non deterministic PDA represents, non deterministic. CFG, since NDCFG and CFG are proper subsets so conversion required.