Formal Languages And Automation Theory MCQs
Set VI
Q1. Regular expression are
a) Type 0 language ✔
b) Type 1 language
c) Type 2 language
d) Type 3 language
Answer is a) Type 0 language
Explanation : According to Chomsky hierarchy regular expression are Type 0 language
Q2. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length} ✔
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
Answer is a) {xϵ {0,1} *|x is all binary number with even length}
Explanation : The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.
Q3. According to the given language, which among the following expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)^4
b) (0+1)^4
c) (01)^4
d) (0+1+ε)^4 ✔
Answer is d) (0+1+ε)^4
Explanation : The extended notation would be (0+1)^4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
Q4. Consider the following CFG
S ? aB S ? bA
B ? b A ? a
B ? bS A ? aS
B ? aBB A ? bAA
Consider the following derivation
S ? aB
? aaBB
? aaBb
? aabSb
? aabbAb
? aabbab
This derivation is
a) leftmost
b) a rightmost derivation
c) both leftmost and rightmost derivation
d) neither leftmost nor rightmost derivation ✔
Answer is d) neither leftmost nor rightmost derivation
Explanation : For explanation Join the discussion below
Q5. Consider the following language
L = {anbncndn|n = 1}
L is
a) CFL but not regular
b) CSL but not CFL✔
c) regular
d) type 0 language but not type 1
Answer is b) CSL but not CFL
Explanation : For explanation Join the discussion below
Q6. S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of (GATE CS 2009)
a) All palindromes.
b) All odd length palindromes. ✔
c) Strings that begin and end with the same symbol
d) All even length palindromes.
Answer is b) All odd length palindromes.
Explanation : The strings accepted by language are {a, b, aaa, bbb, aba, bab, ..}. All of these strings are odd length palindromes.
Q7. 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)*? (GATE CS 2009)
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.
Answer is c) The set of all strings containing at least two 0’s.
Explanation : The regular expression has two 0’s surrounded by (0+1)* which means accepted strings must have at least 2 0’s.
Q8. 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
Answer is c) 12
Explanation : string of length 0 = Not possible (because y is always present).
string of length 1 = 1 (y)
string of length 2 = 3 (xy,yy,ya)
string of length 3 = 8 (xxy,xyy,yxy,yyy,yaa,yab,xya,yya)
Q9. 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
Answer is a) accepted by DFA
Explanation : All of above machine can accept regular language but all string accepted by machine is regular only for DFA.
Q10. Which of the following conversion is not possible (algorithmically)?
a) regular grammar to context-free grammar
b) nondeterministic FSA to deterministic FSA
c) nondeterministic PDA to deterministic PDA ✔
d) nondeterministic TM to deterministic TM
Answer is c) nondeterministic PDA to deterministic PDA
Explanation : For explanation Join the discussion below
Q11. A regular grammar is
a) context free grammar ✔
b) non context free grammar
c) english grammar
d) none of the mentioned
Answer is a) context free grammar
Explanation : Regular grammar is subset of context free grammar.
Q12. 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)*
Answer is b) [(0+1)-(0b+a1)*(a+b)]*
Explanation : All the three are regular expression except bn.
Q13. The given NFA corresponds to which of the following Regular expressions?
a) (0+1) *(00+11) (0+1) * ✔
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
Answer is a) (0+1) *(00+11) (0+1) *
Explanation : The transition states shown are the result of breaking down the given regular expression in fragments. For dot operation, we change a state, for union (plus) operation, we diverge into two transitions and for Kleene Operation, we apply a loop.
Q14. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive ✔
Answer is d) Recursive
Explanation : If L is recursive enumerable and its complement too if and only if L is recursive.
Q15. Recursive languages are :
a) a proper superset of CFL ✔
b) always recognized by PDA
c) are also called type 0 languages
d) always recognized by FSA
Answer is a) a proper superset of CFL
Explanation : For explanation Join the discussion below
If you have any doubts join the discussion below ,our Moderator will reply to your Queries
Recommended MCQs
Formal Languages And Automation Theory MCQs With Answers - Set I
Formal Languages And Automation Theory MCQs With Answers - Set II
Formal Languages And Automation Theory MCQs With Answers - Set III
Formal Languages And Automation Theory MCQs With Answers - Set IV
Formal Languages And Automation Theory MCQs With Answers - Set V
Formal Languages And Automation Theory MCQs With Answers - Set VII
Java MCQs with Answers Set III
Informatica MCQs with Answers Set I
Informatica MCQs with Answers Set II
Informatica MCQs with Answers Set III
Informatica MCQs with Answers Set IV
Informatica MCQs with Answers Set V
Informatica MCQs with Answers Set VI
Computer Organization and Architecture MCQs with Answers Set I
Computer Organization and Architecture MCQs with Answers Set II
Computer Organization and Architecture MCQs with Answers Set III
If you have any doubts join the discussion below ,our Moderator will reply to your Queries
