1. Find a regular expression for a grammar which generates a language which states : L contains a set of strings starting wth an a and ending with a b, with something in the middle.
a. a(a*Ub*)b
b. a*(aUb)b*
c. a(a*b*)b
d. None of the mentioned
Ans- a. a(a*Ub*)b
2. If the partial derivation tree contains the root as the starting variable, the form is known as:
a. Chomsky hierarchy
b. Sentential form
c. Root form
d. None of the mentioned
Ans- b. Sentential form
3. There exists a Context free grammar such that: X->aX; Which among the following is correct with respect to the given assertion?
a. Left Recursive Grammar
b. Right Recursive Grammar
c. Non Recursive Grammar
d. None of the mentioned
Ans- b. Right Recursive Grammar
4. Context free grammar is called Type 2 grammar because of ______ hierarchy.
a. Greibach
b. Backus
c. Chomsky
d. None of the mentioned
Ans- c. Chomsky
5. The following denotion belongs to which type of language: G=(V, T, P, S)
a. Regular grammar
b. Context free grammar
c. Context Sensitive grammar
d. All of the mentioned
Ans- b. Context free grammar
6. abb*c denotes which of the following?
a. {abnc|n=0}
b. {abnc|n=1}
c. {anbc|n=0}
d. {abcn|n>0}
Ans- b. {abnc|n=1}
7. Which of the following strings is not generated by the given grammar: S->SaSbS|e
a. aabb
b. abab
c. abaabb
d. None of the mentioned
Ans- d. None of the mentioned
8. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a. (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b. (bbbb+aaaa)*
c. ((a+b)(a+b)(a+b)(a+b))*
d. None of the mentioned
Ans- c. ((a+b)(a+b)(a+b)(a+b))*
9. Which of the following strings do not belong the given regular expression? : (a)*(a+cba)
a. aa
b. aaa
c. acba
d. acbacba
Ans- d. acbacba
10. Which of the following is an incorrect regular expression identity?
a. R+f=R
b. eR=e
c. Rf=f
d. None of the mentioned
Ans- b. eR=e
11. Which of the following are non essential while simplifying a grammar?
a. Removal of useless symbols
b. Removal of unit productions
c. Removal of null production
d. None of the mentioned
Ans- d. None of the mentioned
12. Statement 1: Ambiguity is the property of grammar but not the language. Statement 2: Same language can have more than one grammar. Which of the following options are correct with respect to the given statements?
a. Statement 1 is true but statement 2 is false
b. Statement 1 is false but statement 2 is true
c. Both the statements are true
c. Both the statements are false
Ans- c. Both the statements are true
13. Let G=(V, T, P, S); where a production can be written as: S->aAS|a and A->SbA|ba|SS ; Which of the following string is produced by the grammar?
a. aabbaab
b. aabbaa
c. baabab
d. None of the mentioned
Ans- b. aabbaa
14. Which among the following is incorrect with reference to a derivation tree?
a. Every vertex has a label which is a terminal or a variable.
b. The root has a label which can be a terminal.
c. The label of the internal vertex is a variable.
d. None of the mentioned
Ans- b. The root has a label which can be a terminal.
15. CFGs are more powerful than:
a. DFA
b. NDFA
c. Mealy Machine
d. All of the mentioned
Ans- d. All of the mentioned
16. A CFG consist of the following elements:
a. a set of terminal symbols
b. a set of non terminal symbols
c. a set of productions
d. all of the mentioned
Ans- d. all of the mentioned