Q1GATE 2016MCQ

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$

🚀 Solve in Practice Mode

📖 Explanation

The grammar productions are $S \rightarrow Aa$ , $A \rightarrow Ba$ , and $B \rightarrow abc$ .
By applying these rules, we derive the single string: $S \Rightarrow Aa \Rightarrow Baa \Rightarrow abcaa$ .
Since the grammar generates a finite language $L = \{abcaa\}$ , it defines a regular language.
Regular languages are categorized as Type 3 in the Chomsky hierarchy.
As Type 3 is the most restrictive category with the highest numerical value, the grammar is classified as Type 3.

Q2GATE 2015MCQ

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}$ ?

🚀 Solve in Practice Mode

📖 Explanation

Let's derive the smallest possible string from the given regular grammar.
The starting non-terminal is $X_0$ .

$X_0 \to 1X_1$ (The string must start with 1).
From $X_1$ , we can choose $X_1 \to 1X_2$ to introduce another 1. The string is now $11X_2$ .
From $X_2$ , we can choose the terminal production $X_2 \to \lambda$ (the empty string).
This gives the shortest string as $11$ .

Now, we check which of the given regular expressions can generate the string "11".
In option C, $1(0 + 10)^*1$ , if the part in the Kleene star $(0+10)^*$ is repeated zero times, the expression simplifies to $1(\lambda)1 = 11$ . None of the other options can generate this simple string.

Q3GATE 2007MCQ

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?

🚀 Solve in Practice Mode

📖 Explanation

Statement P: "Every regular grammar is LL(1)". Regular grammars can be left-recursive, for example, $A \rightarrow A a | b$ . Left-recursive grammars are not LL(1). Thus, P is false.

Statement Q: "Every regular set has a LR(1) grammar". Every regular set (language) is a context-free language. It is a fundamental result that every context-free language has an LR(1) grammar (though not every context-free grammar is LR(1)). Therefore, every regular set has an LR(1) grammar. Thus, Q is true.

Since P is false and Q is true, the correct option is C.

Q4GATE 2006MCQ

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

🚀 Solve in Practice Mode

Q5GATE 2004MCQ

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

🚀 Solve in Practice Mode

Q6MSQ

Choose the correct alternatives (More than one may be correct). Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:

🚀 Solve in Practice Mode

Regular Grammarr Practice Questions

Get the full Regular Grammarr experience — 100% free