** 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**