Type Here to Get Search Results !

# Formal Languages And Automation Theory MCQs With Answers - Set VI

0

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

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

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

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

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 II

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