Recent questions tagged goclasses-toc-practice-questions

Consider the right-linear grammar,$$\begin{aligned}A &\to fB \mid gA \\B &\to gA \mid fC \mid f \\C &\to gA \mid fC \mid f\end{aligned}$$When this grammar is converted in...

Which of the following statements are correct for converting a finite automaton into an equivalent right-linear grammar?Each automaton state becomes a non-terminal. The s...

Consider the NFA given below: Which right-linear grammar is obtained by the standard NFA-to-grammar construction?$q_0 \to aq_1$,$q_1 \to aq_0 \mid bq_1 \mid \epsilon$ $q_...

Consider the right-linear grammar,$$\begin{aligned}S &\to aB \mid bS \mid \epsilon \\B &\to aS \mid bB\end{aligned}$$Which NFA is obtained by the standard grammar-to-NFA ...

Consider the right-linear grammar,$$\begin{aligned}S &\to aT \\T &\to abcS \mid b\end{aligned}$$If this grammar is converted into an NFA with one input symbol per transit...

Let $G$ have start symbol $q_0$ and productions :$$\begin{aligned}q_0 &\to \epsilon \mid abq_0 \mid cq_1\\q_1 &\to ab\end{aligned}$$Which regular expression denotes $L(G)...

Which of the following statements are always true?Every language generated by a regular grammar is regular. Every regular language can be generated by a regular grammar. ...

Consider the grammar with start variable $A$ and productions :$$\begin{aligned}A &\to aB \mid bA \\B &\to bA \mid aC \mid a \\C &\to bA \mid aC \mid a\end{aligned}$$Which...

Consider the grammar $G$ with productions :$$\begin{aligned}S &\to aB \mid \epsilon \\B &\to Sbb\end{aligned}$$Which option is correct?$L(G)=\{a^n b^{2n}\mid n\ge 0\}$ an...

Consider the grammar $G$ with start variable $A$ and productions $:$$$\begin{aligned}A &\to aB \mid bC \\B &\to aB \mid \epsilon \\C &\to aD \mid A \mid bC \\D &\to aD \m...

Consider the following grammar$$\begin{aligned}S &\to AA \\A &\to AAA \mid bA \mid Ab \mid a\end{aligned}$$Which of the following strings can be used as a witness to show...

Which CFG generates the set of all properly balanced strings of parentheses, including $\epsilon$, the parentheses must be properly nested. Some sample strings in the lan...

Let's imagine that you're going for a walk with your dog, but this time don't have a leash. Let $\Sigma = \{y,d\}$, where $y$ means that you take a step forward and $d$ m...

Let $\Sigma = \{1,+,=\}$ then which of the following CFG generates the language $L = \{1^m+1^n=1^{m+n} \mid m,n \in \mathbb{N}\}$. For example, the strings $111+1=1111$ a...

Let $\Sigma = \{a,b\}$ and $L = \{w \in \Sigma^* \mid w$ is not a palindrome$\}$, i.e, the language of strings that are not the same when read forwards and backwards. For...

Consider the CFG$$\begin{aligned}S &\to VS \mid cT \\T &\to VT \mid cU \\U &\to \epsilon \mid VU \\V &\to a \mid b\end{aligned} $$Which language is generated by this gram...

Which CFG generates the language $L = \{a^m b^n \mid 2m=n \text{ or } m=2n\}$?$S \to aSbb \mid aaSb \mid \epsilon$ $S \to X \mid Y$$X \to aXbb \mid \epsilon$$Y \to aaYb \...

Which CFG generates the language $L = \{a^i b^j c^k \mid i+k=j\}$?$S \to AB$ $A \to aAb \mid \epsilon$ $B \to bBc \mid \epsilon$ $S \to aSb \mid bSc \mid \epsilon$ $S \to...

Which CFG generates the language $L = \{(a^*b)^i c^i \mid i 0\}$?$S \to AbSc \mid Abc$$A \to aA \mid \epsilon$ $S \to AbS \mid Abc$ $A \to aA \mid \epsilon$ $S \to AbcS ...

Let $\Sigma = {a,b,c}$. Which CFG generates the language $L = \{w \in \Sigma^* \mid w$ contains $aa$ as a substring$\}$?$S \to XaaX, ~~X \to aX \mid bX \mid cX \mid \epsi...

Let $P,Q$ and $R$ be regular expressions such that the number of strings generated by $P$ is $p$, $Q$ is $q$ and $R$ is $r$. What is the number of strings generated by th...

Select the equivalent regular expression for the given $\epsilon$-NFA.$(01)^*1(01)$  $(0+1)^*1(0+1)$  $((0+1)^*+1)(0+1)$  $(01)^*+1+(01)$

$(1(0+1)^*1)^*$ denotes all strings that start and end with $1$.True False

Which of the following languages are regular?$L_1 = \{x \mid x$ has two $0$s separated by the number of positions that is a multiple of $4\}$ $L_2 = \{x \mid x$ is binary...

Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all prefixes of $w$. Minimum number of states in an NFA that accepts $L$ is?$n-1$ $n$ $n+1$ $2n-...

Which of the following languages is non-regular? $(w^R$ is the reverse of string $w)$$L_1 = \{ww^R \mid w \in \{0,1\}^*\}$  $L_2 = \{ww^Rx \mid w,x \in \{0,1\}^*\}$  $L_3...

The minimum state automaton equivalent to the DFA below has how many states? 

Which of the following languages is non-regular? $L_1 = \{x \mid x \in \{a,b\}^*$ and $x$ has even number of $b\}$  $L_2 = \{x \mid x \in \{a,b,c\}^*$ and $x$ has no $c$ ...

Let $\Sigma = \{a\}$. Consider the language $L = \{a^{nk} \mid k 0,\ n$ is a positive integer constant$\}$. What is the minimum number of states in a DFA that recognises...

Suppose $\Sigma = \{0,1\}$, $L_1 = \{w \mid w$ does not contain the string $01\}$ and $L_2 =\{w \mid w$ contains the string $01\}$. Let the corresponding DFAs for $L_1$ a...