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


There are 5 questions to complete.

Leave a Comment