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

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


Post a comment

0 Comments

Top Post Ad

Below Post Ad