Type Here to Get Search Results !

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

0

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

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

Explanation : For explanation Join the discussion below

Q4. The following CFG is in

S ? AB
B ? CD
B ? b
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

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

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

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

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

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.