1. Which of the following String can be obtained by the language L = {ai b2i / i >=1}?
a) aaabbbbbb
b) aabbb
c) abbabbba
d) aaaabbbabb
Explanation: Above production rule gives suppose if 3 a’s the corresponding b’s are 6 b’s.
2. Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.
a) {S->bS, S->b,S->aA, S->bA, A->aB, B->bB, B->aS, S->a}
b) {S->aS,S->bA,A->bB,B->bBa,B->bB}
c) {S->aaS,S->bbA,A->bB,B->ba}
d) None of the mentioned
Explanation: The above given condition is satisfied by
S->bS S->B
S->aA s->bA A->aB B->bB
B->aS S->a.
3. The production Grammar is {S->aSbb, S->abb} is?
a) type-3 grammar
b) type-2 grammar
c) type-1 grammar
d) type-0 grammar
Explanation: Type 2 grammar satisfies this production grammar.
4. The regular expression denote a language comprising all possible strings of even length over the alphabet (0,1) is?
a) 1 + 0(1+0)*
b) (0+1)(1+0)*
c) (1+0)
d) (00+0111+10)*
Explanation: The condition is satisfied by 00 or 0111 or 10 or iterations of these.
5. Left Linear grammar can be converted to Right Linear grammar.
a) Yes
b) No
Explanation: Since right-linear grammars are regular, it follows that left-linear grammars are also regular.
6. What is CFG?
a) Compiler
b) A language expression
c) Regular Expression
d) None of the mentioned
Explanation: They are defined by rule A->b where A is non terminal and b is terminal.
7. What is the idea of automation with a stack as auxiliary storage?
a) Finite automata
b) Push Down Automata
c) Deterministic Automata
d) None of the mentioned
Explanation: Push Down Automata manipulate the Stack as a part of performing a transition.
8. Transition of finite automata is ___________
a) Finite Diagram
b) State Diagram
c) Node Diagram
d) E-R Diagram
Explanation: Transition of finite automata is Finite Diagram.
9. A context free language is called ambiguous if?
a) It has 2 or more than 2 left derivations for some terminal string ѡ є L (G)
b) It has 2 or more than 2 right derivations for some terminal string ѡ є L (G)
c) It has 2 or more than 2 left and right derivations for some terminal string ѡ є L (G)
d) None of the mentioned
Explanation: When two or more Left and right most derivative occur the grammar turn ambiguous .
10. Which of the following statement is true?
a) Every language that is defined by regular expression can also be defined by finite automata
b) Every language defined by finite automata can also be defined by regular expression
c) We can convert regular expressions into finite automata
d) All of the mentioned
Explanation: All these statements are true w.r.t regular expression.