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

^{n}b^^{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^**

^{n}b^

^{m}c^

^{p}d^

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