Recent questions tagged regular-language

Let \(I \subseteq \Sigma^*\) be any nonregular language.For every string \(w \notin I\), define $R_w = \Sigma^* - \{w\}.$Now consider $K = \bigcap_{w \notin I} R_w.$What ...

For every $n\geq 0$, define $L_n=\{a^nb^n\}$.Which statement is correct?Every $L_n$ is nonregular, but $\bigcup_{n=0}^{\infty}L_n$ is regular. Every $L_n$ is regular, and...

Let $\Sigma=\{0,1\}.$Which of the following are valid examples?$A=\{01\}, \qquad B=\{0^n1^n\mid n\ge0\}$where $A$ is regular, $B$ is nonregular, and $A\subseteq B$. $C=\{...

Suppose $L_1$ and $L_2$ are both nonregular languages.Which statement about $L_1\cup L_2$ is correct?It must be nonregular. It must be regular. It may be regular or nonre...

Let $L$ be a nonregular language.What can always be concluded about $L^R$?$L^R$ is regular. $L^R$ is nonregular. $L^R$ may be regular or nonregular. Nothing can be conclu...

Let $L$ be a context-free language and $R$ be a regular language.Consider the problem$$L-R=\varnothing?$$Which statement is correct?It is decidable because $L-R$ is conte...

For languages $X,Y\subseteq\Sigma^*$, define$$X/Y = \{w:\exists y\in Y,\ wy\in X\}$$ Suppose $X$ is regular, but nothing is assumed about $Y$.Which statement is always tr...

Let $X$ and $Y$ be regular languages. Their symmetric difference is$$X\triangle Y=\{w:w\text{ belongs to exactly one of }X,Y\}$$. Which expression correctly represents $X...

Let $M$ and $N$ be two DFAs. Define$$Z=\{u_1v_1u_2v_2\cdots u_kv_k : k\ge0, ~u_i\in L(M), ~v_i\in L(N)\}.$$Which regular-language expression describes $Z$?$L(M)^*L(N)^*$ ...

Let $L$ be an arbitrary regular language over $\Sigma$, and define$$K=\{w\in\Sigma^*:w^Rw\in L\}$$.Which statement is correct?$K$ is always regular. $K$ is regular only i...

For an arbitrary language $L$, which of the following statements is correct?If $L^*$ is regular, then $L$ must be regular. If $L$ is nonregular, then $L^*$ must be nonreg...

Let $L_1$ and $L_2$ be regular languages and let $L_3$ be non-regular. Which statements are always true?$L_1=L_2$ iff $L_1\cap\overline{L_2}=\emptyset$ $L_1\cup L_3$ is n...

Which statements are true?Every language recognized by an $n$-state DFA can be recognized by an NFA with $n$ states. Every language recognized by an $n$-state NFA can be ...

Let $L_1$ be regular where specified. Which of the following languages are guaranteed to be regular?$\{ww\mid w\in{0,1}^*\}$ $\{ww\mid w\in L_1\}$ $\{w\mid ww\in L_1\}$ $...

All languages are over $\{0,1\}$. Which statements are true?If $L_1\subseteq L_2$ and $L_2$ is regular, then $L_1$ must be regular. If $L_1$ and $L_2$ are both non-regula...

Which classification is correct?$\{w\in \{0,1\}^* \mid \#0(w)=\#1(w)\}$ is regular.  $\{w\in \{0,1\}^* \mid \#0(w)=\#1(w)\}$ is not regular.  $\{w\in \{0,1\}^* \mid \#01(...

For $L=\{a^n b^n\mid n\ge0\}$, which choice correctly proves non-regularity using Myhill-Nerode?Use $S=\{a^i\mid i\ge0\}$ and distinguish $a^i$ from $a^j$ using suffix $b...

Let $L=\{w\in{0,1}^*\mid w$ contains equal numbers of substrings $01$ and $10\}$. Which statements are correct?$L$ is regular. A correct regular expression for $L$ is $\e...

Let $L_n=\{0^n1^n\}$ for each $n\ge0$. Which statements are correct?Each $L_n$ is regular. Any finite union of such languages is regular. $\bigcup_{n\ge0}L_n=\{0^n1^n\mid...

Let $L_1$ be a DCFL and $R$ be a regular language over the same alphabet. Which languages are guaranteed to be DCFL?$L_1\cap R$ $L_1\cup R$ $L_1-R$ $L_1^R$ $L_1\cap L_2$,...

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

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

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

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

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason RAssertion A: If $L$ is regular, then its compliment $L^{\prime}$ is ne...

Arrange the following in the order of execution while proving a Language is non-Regular using Pumping Lemma.Split in to $x y z$ satisfying pumping Lemma conditions.Assume...

If $r_{1}$ and $r_{2}$ are regular expressions, then which of the following are correct.$\mathrm{L}\left(\mathrm{r}_{1}+\mathrm{r}_{2}\right)=\mathrm{L}\left(\mathrm{r}_{...