Regular Grammars Questions-Answers – Theory of Computation
Q1 |Regular GrammarsConsider the grammar given below S → x B | y A A → x | x S | y A A B → y | y S | y B B Consider the following strings. (i) xxyyx (ii) xxyyxy (iii) xyxy (iv) yxxy (v) yxx (vi) xyx Which of the above strings are generated by the grammar ? |
| i ➥ (i), (iii), and (iv) |
| ii ➥ (ii), (iii), and (iv) |
| iii ➥ (ii), (v), and (vi) |
| iv ➥ (i), (ii), and (iii) |
Show Answer With Best Explanation
| Q2 |Regular Grammars The two grammars given below generate a language over the alphabet {x, y, z} G1: S → x|z|xS|zS|yB B → y|z|yB|zB G2: S → y|z|yS|zS|xB B → y|yS Which one of the following choices describes the properties satisfied by the strings in these languages? |
| i ➥ G1 : No y appears after any x G2 : Every y is followed by at least one x |
| ii ➥ G1 : No y appears after any x G2 : Every x is followed by at least one y |
| iii ➥ G1 : No y appears before any x G2 : No x appears before any y |
| iv ➥ G1 : No y appears before any x G2 : Every x is followed by at least one y |
Show Answer With Best Explanation
| Q3 |Regular Grammars Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ? |
| i ➥ L (D) = L (G) |
| ii ➥ L (D) ⊂ L (G) |
| iii ➥ L (D) ⊃ L (G) |
| iv ➥ L (D) is empty |
Show Answer With Best Explanation
| Q4 |Regular Grammars Which of the following conversions is not possible (algorithmically)? |
| i ➥ Non-deterministic Turing machine to deterministic Turing machine |
| ii ➥ Non-deterministic PDA to deterministic PDA |
| iii ➥ Non-deterministic FSA to deterministic FSA |
| iv ➥ Regular grammar to context free grammar |
Show Answer With Best Explanation
| Q5 |Regular Grammars In the following grammar X ::= X ⊕ Y/Y Y ::= Z * Y/Z Z ::= id Which of the following is true? |
| i ➥ ‘⊕’ is left associative while ‘*’ is right associative |
| ii ➥ ‘⊕’ is right associative while ‘*’ is left associative |
| iii ➥ Both ‘⊕’ and ‘*’ is left associative |
| iv ➥ None of the above |
Show Answer With Best Explanation
| Q6 |Regular Grammars A grammar that is both left and right recursive for a non-terminal, is |
| i ➥ Ambiguous |
| ii ➥ Unambiguous |
| iii ➥ Information is not sufficient to decide whether it is ambiguous or unambiguous |
| iv ➥ None of the above |
Show Answer With Best Explanation
| Q7 |Regular Grammars Given the following expression grammar: E → E * F | F + E | F F → F – F | id which of the following is true? |
| i ➥ – has higher precedence than * |
| ii ➥ * has higher precedence than + |
| iii ➥ +and – have same precedence |
| iv ➥ +has higher precedence than * |
Show Answer With Best Explanation
| Q8 |Regular Grammars Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar? |
| i ➥ Removing left recursion alone |
| ii ➥ Factoring the grammar alone |
| iii ➥ Removing left recursion and factoring the grammar |
| iv ➥ None of the above |
Show Answer With Best Explanation
| Q9 |Regular Grammars Consider the following grammar G: S → bS| aA| b A → bA| aB B → bB| aS |a Let Na(w) and Nb(w) denote the number of a’s and b’s in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is |
| i ➥ {w|Nb(w) = 3k, k ∈ {0, 1, 2, …}} |
| ii ➥ {w|Na(w) = 3k, k ∈ {0, 1, 2, …}} |
| iii ➥ {w|Nb(w) > 3Na(w)} |
| iv ➥ {w|Na(w) > 3Nb(w)} |
Show Answer With Best Explanation
| Q10 |Regular Grammars Consider the grammar with the following translation rules and E as the start symbol. E → E1 # T {E.value = E1.value * T.value} | T {E.value = T.value} T → T1 & F {T.value = T1.value + F.value} | F {T.value = F.value} F → num {F.value = num.value} Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4. |
| i ➥ 40 |
| ii ➥ 160 |
| iii ➥ 180 |
| iv ➥ 200 |
Show Answer With Best Explanation
| Q11 |Regular Grammars Consider the grammar: E → E + n | E × n | n For a sentence n + n × n, the handles in the right-sentential form of the reduction are: |
| i ➥ n, E + n and E × n |
| ii ➥ n, n + n and n + n × n |
| iii ➥ n, E + n and E + E × n |
| iv ➥ n, E + n and E + n × n |
Show Answer With Best Explanation
| Q12 |Regular Grammars In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string albm with l≠m? |
| i ➥ max(l, m)+3 |
| ii ➥ l+m+3 |
| iii ➥ l+m+2 |
| iv ➥ max(l,m)+2 |
Show Answer With Best Explanation
| Q13 |Regular Grammars Which one of the following grammars generates the language L = {aibj|i≠j}? |
| i ➥ S→AC|CB C→aCb|a|b A→aA|ϵ B→Bb|ϵ |
| ii ➥ S→aS|Sb|a|b |
| iii ➥ S→AC|CB C→aCb|ϵ A→aA|ϵ B→Bb|ϵ |
| iv ➥ S→AC|CB C→aCb|ϵ A→aA|a B→Bb|b |
Show Answer With Best Explanation
| Q14 |Regular Grammars Consider the CFG with {S,A,B} as the non-terminal alphabet, {a,b} as the terminal alphabet, S as the start symbol and the following set of production rules: S → aB S → bA B → b A → a B → bS A → aS B → aBB A → bAA Which of the following strings is generated by the grammar? |
| i ➥ abbbba |
| ii ➥ aabbab |
| iii ➥ aabbbb |
| iv ➥ aaaabb |
Show Answer With Best Explanation
| Q15 |Regular Grammars How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*? |
| i ➥ 7 |
| ii ➥ 10 |
| iii ➥ 12 |
| iv ➥ 11 |
Show Answer With Best Explanation
| Q16 |Regular Grammars Which of the following is true? |
| i ➥ (01)*0 = 0(10)* |
| ii ➥ (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)* |
| iii ➥ (0+1)*01(0+1)*+1*0* = (0+1)* |
| iv ➥ All |
Show Answer With Best Explanation
| Q17 |Regular Grammars A language is regular if and only if? |
| i ➥ Accepted by Turing machine |
| ii ➥ Accepted by LBA |
| iii ➥ Accepted by PDA |
| iv ➥ Accepted by DFA |
Show Answer With Best Explanation
| Q18 |Regular Grammars What is Regular grammar? |
| i ➥ Context free grammar |
| ii ➥ Non context free grammar |
| iii ➥ English grammar |
| iv ➥ None of the mentioned |
Show Answer With Best Explanation
| Q19 |Regular Grammars Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then? |
| i ➥ L1<l2 |
| ii ➥ L1>=L2 |
| iii ➥ L1 U L2 = .* |
| iv ➥ L1=L2 |
Show Answer With Best Explanation
| Q20 |Regular Grammars Which of the following is not a regular expression? |
| i ➥ [(a+b)*-(aa+bb)]* |
| ii ➥ [(0+1)-(0b+a1)*(a+b)]* |
| iii ➥ (01+11+10)* |
| iv ➥ (1+2+0)*(1+2)* |
Show Answer With Best Explanation
| Q21 |Regular Grammars Regular expression is_______. |
| i ➥ Type 3 language |
| ii ➥ Type 2 language |
| iii ➥ Type 1 language |
| iv ➥ Type 0 language |
Show Answer With Best Explanation
| Q22 |Regular Grammars Which of the following is true? |
| i ➥ Infinite times union of finite set is always regular |
| ii ➥ Union of two non regular set of language is not regular |
| iii ➥ All finite subsets of non-regular set are always regular |
| iv ➥ All subsets of a regular set are always regular |
Show Answer With Best Explanation
| Q23 |Regular Grammars L and ~L are recursive enumerable then L is? |
| i ➥ Recursive |
| ii ➥ Context sensitive |
| iii ➥ Regular |
| iv ➥ Context free |
Show Answer With Best Explanation
| Q24 |Regular Grammars Regular expressions are closed under_____. |
| i ➥ Kleene star |
| ii ➥ Intersection |
| iii ➥ Union |
| iv ➥ All of the mentioned |
Show Answer With Best Explanation
| Q25 |Regular Grammars Which of the following String can be obtained by the language L = {ai b2i / i >=1}? |
| i ➥ abbabbba |
| ii ➥ aaaabbbabb |
| iii ➥ aaabbbbbb |
| iv ➥ aabbb |
Show Answer With Best Explanation
| Q26 |Regular Grammars Let R1 and R2 be regular sets defined over alphabet ∑ then? |
| i ➥ R1 UNION R2 is regular |
| ii ➥ R1 INTERSECTION R2 is regular |
| iii ➥ ∑ INTERSECTION R2 IS NOT REGULAR |
| iv ➥ R2* IS NOT REGULAR |
Show Answer With Best Explanation
| Q27 |Regular Grammars Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}. |
| i ➥ {S->bS, S->b,S->aA, S->bA, A->aB, B->bB, B->aS, S->a} |
| ii ➥ {S->aS,S->bA,A->bB,B->bBa,B->bB} |
| iii ➥ {S->aaS,S->bbA,A->bB,B->ba} |
| iv ➥ None of above |
Show Answer With Best Explanation
| Q28 |Regular Grammars The production Grammar is {S->aSbb, S->abb} is? |
| i ➥ type-0 grammar |
| ii ➥ type-1 grammar |
| iii ➥ type-2 grammar |
| iv ➥ type-3 grammar |
Show Answer With Best Explanation
| Q29 |Regular Grammars The regular expression denote a language comprising all possible strings of even length over the alphabet (0,1) is? |
| i ➥ (00+0111+10)* |
| ii ➥ (1+0) |
| iii ➥ (0+1)(1+0)* |
| iv ➥ 1 + 0(1+0)* |
Show Answer With Best Explanation
| Q30 |Regular Grammars |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
| You should also practice on below topics Regular Language Mode Deterministic Finite Automaton (DFA), Non-Deterministic Finite Automaton (NDFA), Equivalence of DFA and NDFA, Regular Languages, Regular Grammars, Regular Expressions, |