# Regular Grammar

 Question 1
What is the highest type number that can be assigned to the following grammar?
$S \rightarrow A a, A \rightarrow B a, B \rightarrow a b c$
 A Type 0 B Type 1 C Type 2 D Type 3
ISRO CSE 2016   Theory of Computation
Question 1 Explanation:
 Question 2
Consider the alphabet $\Sigma$={0, 1}, the null/empty string $\lambda$ and the sets of strings $X_{0}, X_{1}, \; and \; X_{2}$ generated by the corresponding non-terminals of a regular grammar. $X_{0}, X_{1}, \; and \; X_{2}$ are related as follows.
$X_{0}=1X_{1}$
$X_{1},=0X_{1}+1 X_{2}$
$X_{2}=0X_{1}+ \{\lambda\}$
Which one of the following choices precisely represents the strings in $X_{0}$?
 A 10(0* + (10)*)1 B 10(0* + (10)*)*1 C 1(0 + 10)*1 D 10(0 + 10)*1 + 110(0 + 10)*1
GATE CSE 2015 SET-2   Theory of Computation
Question 2 Explanation:
 Question 3
Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?
 A Both P and Q are true B P is true and Q is false C P is false and Q is true D Both P and Q are false
GATE CSE 2007   Theory of Computation
Question 3 Explanation:
 Question 4
Consider the regular grammar below
$S \rightarrow bS \mid aA \mid \epsilon$
$A \rightarrow aS \mid bA$
The Myhill-Nerode equivalence classes for the language generated by the grammar are
 A $\{w \in (a + b)^* \mid \#a(w) \text{ is even) and} \{w \in (a + b)^* \mid \#a(w) \text{ is odd}\}$ B $\{w \in (a + b)^* \mid \#a(w) \text{ is even) and} \{w \in (a + b)^* \mid \#b(w) \text{ is odd}\}$ C $\{w \in (a + b)^* \mid \#a(w) = \#b(w) \text{and }\{w \in (a + b)^* \mid \#a(w) \neq \#b(w)\}$ D $\{\epsilon\},\{wa \mid w \in (a + b)^* \text{and} \{wb \mid w \in (a + b)^*\}$
GATE IT 2006   Theory of Computation
Question 4 Explanation:
 Question 5
Consider the following grammar G:

Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively.
The language $L(G)\subseteq \{a,b\}^{+}$ generated by G is
 A { w | Na(w) $\gt$ 3Nb(w)} B { w | Nb(w) $\gt$ 3Na(w)} C { w | Na(w) = 3k, k $\in$ {0, 1, 2, ...}} D { w | Nb(w) = 3k, k $\in$ {0, 1, 2, ...}}
GATE CSE 2004   Theory of Computation
Question 5 Explanation:
 Question 6
Choose the correct alternatives (More than one may be correct).
Let $R_{1}$ and $R_{1}$ be regular sets defined over the alphabet $\Sigma$ Then:
 A $R_{1} \cap R_{2}$ is not regular. B $R_{1} \cup R_{2}$ is regular. C $\Sigma^{*}-R_{1}$ is regular. D $R_{1}^{*}$ is not regular.
GATE CSE 1990   Theory of Computation
Question 6 Explanation:
There are 6 questions to complete.