Formal Language & Automata Theory

40 Questions | Total Attempts: 259

SettingsSettingsSettings
Please wait...
Formal Language & Automata Theory

.


Questions and Answers
  • 1. 
    Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
    • A. 

      ScT (S is a subset of T)

    • B. 

      TcS (T is a subset of S)

    • C. 

      S=T

    • D. 

      SnT=Ø

  • 2. 
    Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
    • A. 

      L = O

    • B. 

      L is regular but not O

    • C. 

      L is context free but not regular

    • D. 

      L is not context free

  • 3. 
    Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?
    • A. 

      Only S1 is correct

    • B. 

      Only S2 is correct

    • C. 

      Both S1 and S2 are correct

    • D. 

      None of S1 and S2 is correct

  • 4. 
    Which of the following statements in true?
    • A. 

      If a language is context free it can always be accepted by a deterministic push-down automaton

    • B. 

      The union of two context free languages is context free

    • C. 

      The intersection of two context free languages is context free

    • D. 

      The complement of a context free language is context free

  • 5. 
     Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.
    • A. 

      N^2

    • B. 

      2^N

    • C. 

      2N

    • D. 

      N!

  • 6. 
     Let L={w  (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
    • A. 

      (0*10*1)*

    • B. 

      0*(10*10*)*

    • C. 

      0*(10*1*)*0*

    • D. 

      0*1(10*1)*10*

  • 7. 
     Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
    • A. 

      L2 – L1 is recursively enumerable.

    • B. 

      L1 – L3 is recursively enumberable

    • C. 

      L2 \cap L1 is recursively enumberable

    • D. 

      L2 \cup L1 is recursively enumberable

  • 8. 
     Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i = 2j+1}, L4 = {|i != 2j}. Which one of the following statements is true?
    • A. 

      Only L2 is context free

    • B. 

      Only L2 and L3 are context free

    • C. 

      Only L1 and L2 are context free

    • D. 

      All are context free

  • 9. 
     Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
    • A. 

      n-1

    • B. 

      N

    • C. 

      N+1

    • D. 

      2n-1

  • 10. 
    Given the language L = {ab, aa, baa}, whih of the following strings are in L*?….1) abaabaaabaa….2) aaaabaaaa….3) baaaaabaaaab….4) baaaaabaa
    • A. 

      1, 2 and 3

    • B. 

      2, 3 and 4

    • C. 

      1, 2 and 4

    • D. 

      1, 3 and 4

  • 11. 
     Which of the following problems are decidable?….1) Does a given program ever produce an output?….2) If L is a context-free language, then is L’ (complement of L) also context-free?….3) If L is a regular language, then is L’ also regular?….4) If L is a recursive language, then, is L’ also recursive?
    • A. 

      1, 2, 3, 4

    • B. 

      1, 2

    • C. 

      2, 3, 4

    • D. 

      3, 4

  • 12. 
    Let P be a regular language and Q be context-free language such that Q  P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn|n  N}). Then which of the following is ALWAYS regular? 
    • A. 

      P   Q

    • B. 

      P – Q

    • C. 

      * – P

    • D. 

      * – Q

  • 13. 
     Consider the language L1,L2,L3 as given below.L1={ | p,q  N}L2={ | p,q  N and p=q}L3={ | p,q,r  N and p=q=r}Which of the following statements is NOT TRUE?
    • A. 

      Push Down Automata (PDA) can be used to recognize L1 and L2

    • B. 

      L1 is a regular language

    • C. 

      All the three languages are context free

    • D. 

      Turing machine can be used to recognize all the three languages

  • 14. 
    S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
    • A. 

      All palindromes.

    • B. 

      All odd length palindromes.

    • C. 

      Strings that begin and end with the same symbol

    • D. 

      All even length palindromes.

  • 15. 
     Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
    • A. 

      The set of all strings containing the substring 00.

    • B. 

      The set of all strings containing at most two 0’s.

    • C. 

      The set of all strings containing at least two 0’s.

    • D. 

      The set of all strings that begin and end with either 0 or 1.

  • 16. 
     Which one of the following is FALSE?
    • A. 

      There is unique minimal DFA for every regular language

    • B. 

      Every NFA can be converted to an equivalent PDA.

    • C. 

      Complement of every context-free language is recursive.

    • D. 

      Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

  • 17. 
    Match all items in Group 1 with correct options from those given in Group 2.Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization 
    • A. 

      P-4. Q-1, R-2, S-3

    • B. 

      P-3, Q-1, R-4, S-2

    • C. 

      P-3, Q-4, R-1, S-2

    • D. 

      P-2, Q-1, R-4, S-3

  • 18. 
    How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
    • A. 

      7

    • B. 

      10

    • C. 

      12

    • D. 

      11

  • 19. 
     Which of the following is true?
    • A. 

      (01)*0 = 0(10)*

    • B. 

      (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*

    • C. 

      (0+1)*01(0+1)*+1*0* = (0+1)*

    • D. 

      All of the mentioned

  • 20. 
    A language is regular if and only if
    • A. 

      Accepted by DFA

    • B. 

      Accepted by PDA

    • C. 

      accepted by LBA

    • D. 

      Accepted by Turing machine

  • 21. 
     Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
    • A. 

      L1

    • B. 

      L1>=L2

    • C. 

      L1 U L2 = .*

    • D. 

      L1=L2

  • 22. 
    Which of the following is not a regular expression?
    • A. 

      [(a+b)*-(aa+bb)]*

    • B. 

      [(0+1)-(0b+a1)*(a+b)]*

    • C. 

      (01+11+10)*

    • D. 

      (1+2+0)*(1+2)*

  • 23. 
     Regular expression are
    • A. 

      Type 0 language

    • B. 

      Type 1 language

    • C. 

      Type 2 language

    • D. 

      Type 3 language

  • 24. 
    Which of the following is true?
    • A. 

      Every subset of a regular set is regular

    • B. 

      Every finite subset of non-regular set is regular

    • C. 

      The union of two non regular set is not regular

    • D. 

      Infinite union of finite set is regular

  • 25. 
    L and ~L are recursive enumerable then L is
    • A. 

      Regular

    • B. 

      Context free

    • C. 

      Context sensitive

    • D. 

      Recursive