Formal Languages And Automation Theory MCQs
Set VII
Q1. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA ✔
Answer is d) B->bA
Explanation : Some derivations are not reachable from the starting variable. As B is not reachable from the starting variable, it is a useless symbol and thus, can be eliminated.
Q2. Consider the following language
L = {a^nb^n|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 a) CFL but not regular
Explanation : For explanation Join the discussion below
Q3. Consider the following language
L = {a^nb^mc^pd^q|n, m, p, q = 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 c) regular
Explanation : For explanation Join the discussion below
Q4. The following CFG is in
S ? AB
B ? CD
B ? AD
B ? b
D ? AD
D ? d
A ? a
C ? a
a) Chomsky normal form but not strong Chomsky normal form
b) Weak Chomsky normal form but not Chomsky normal form
c) Strong Chomsky normal form ✔
d) Greibach normal form
Answer is c) Strong Chomsky normal form
Explanation : For explanation Join the discussion below
Q5. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below: (GATE CS 2009)
L1 = {a^mb^mca^nb^n | m, n >= 0 }
L2 = {a^ib^jc^k | i, j, k >= 0 }
Then L is :
a) Not recursive
b) Regular
c) Context free but not regular ✔
d) Recursively enumerable but not context free.
Answer is c Context free but not regular
Explanation : The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is L1 ∩L2 = {a^kb^kc | k >= 0} which is context free, but not regular.
Q6. 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
Answer is b) P-3, Q-1, R-4, S-2
Explanation : For explanation Join the discussion below
Q7. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1 ✔
b) 3/4
c) 2/3
d) 0
Answer is a) 1
Explanation : A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will never produce a string to the grammar.
Q8. The following CFG is in
S ? aBB
B ? bAA
A ? a
B ? b
a) Chomsky normal form but not strong Chomsky normal form
b) Weak Chomsky normal form but not Chomsky normal form
c) Strong Chomsky normal form
d) Greibach normal form ✔
Answer is d) Greibach normal form
Explanation : For explanation Join the discussion below
Q9. Which of the following CF language is inherently ambiguous?
a) {anbncmdm|n, m = 1}
b) {anbmcpdq|n = p or m = q, n, m, p, q = 1} ✔
c) {anbmcpdq|n ? m ? p ? q}
d) {anbmcpdq|n ? m ? p ? q}
Answer is b) {anbmcpdq|n = p or m = q, n, m, p, q = 1}
Explanation : For explanation Join the discussion below
Q10. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S} ✔
d) None of the mentioned
Answer is c) {A,B,S}
Explanation : First step: Make a set of variables that directly end up with a terminal
Second step: Modify the set with variables that produce the elements of above
generated set.
The rest variables are termed as useless.
Q11. 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. ✔
Answer is d) Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Explanation : Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.
Q12. Can a DFSA simulate a NFSA
a) No
b) Yes ✔
c) sometimes
d) depends on NFA
Answer is b) Yes
Explanation : For explanation Join the discussion below
Q13. Inorder to simplify a context free grammar, we can skip the following operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned ✔
Answer is d) None of the mentioned
Explanation : Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.
Q14. The concept of FSA is much used in this part of the compiler
a) Lexical analysis ✔
b) Parser
c) Code generation
d) Code optimization
Answer is a) Lexical analysis
Explanation : lexical analysis uses the concept of FSA
Q15. The concept of grammar is much used in this part of the compiler
a) Lexical analysis
b) Parser ✔
c) Code generation
d) Code optimization
Answer is b) Parser
Explanation : Parser uses the concept of grammar. a parsing expression grammar (PEG), is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.
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 VI
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
