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

S \rightarrow A a, A \rightarrow B a, B \rightarrow a b c

Type 0 | |

Type 1 | |

Type 2 | |

Type 3 |

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

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

10(0* + (10)*)1 | |

10(0* + (10)*)*1 | |

1(0 + 10)*1 | |

10(0 + 10)*1 + 110(0 + 10)*1 |

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?

P: Every regular grammar is LL(1)

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

Which of the following is TRUE?

Both P and Q are true | |

P is true and Q is false | |

P is false and Q is true | |

Both P and Q are false |

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

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

\{w \in (a + b)^* \mid \#a(w) \text{ is even) and} \{w \in (a + b)^* \mid \#a(w) \text{ is odd}\} | |

\{w \in (a + b)^* \mid \#a(w) \text{ is even) and} \{w \in (a + b)^* \mid \#b(w) \text{ is odd}\} | |

\{w \in (a + b)^* \mid \#a(w) = \#b(w) \text{and }\{w \in (a + b)^* \mid \#a(w) \neq \#b(w)\} | |

\{\epsilon\},\{wa \mid w \in (a + b)^* \text{and} \{wb \mid w \in (a + b)^*\} |

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

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

{ w | Na(w) \gt 3Nb(w)} | |

{ w | Nb(w) \gt 3Na(w)} | |

{ w | Na(w) = 3k, k \in {0, 1, 2, ...}} | |

{ w | Nb(w) = 3k, k \in {0, 1, 2, ...}} |

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:

Let R_{1} and R_{1} be regular sets defined over the alphabet \Sigma Then:

R_{1} \cap R_{2} is not regular. | |

R_{1} \cup R_{2} is regular. | |

\Sigma^{*}-R_{1} is regular. | |

R_{1}^{*} is not regular. |

Question 6 Explanation:

There are 6 questions to complete.