# Recent questions tagged regular-languages

0 votes
0 answers 7 views
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
5 votes
3 answers 1.2K views
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states? $L-\{01\}$ $L \cup \{01\}$ $\{0,1\}^* – L$ $L \cdot L$
4 votes
1 answer 837 views
​​​​​​Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true
0 votes
2 answers 79 views
L =. a^i b^2j | i,j>=1 is regular or not ?
0 votes
1 answer 37 views
What will be the union of L1 U L2 ? L1= {a^n b ^m | n≤m} L2={a^n b^m | n≥m}
0 votes
0 answers 165 views
Set of possible strings generated by Regular expression (11+111)* should contain {null, {11}, {111}, {11111},…}. Can this set contain the strings which are generated considering the part of the above RE partially, i.e., will {1111} (length 4), generated by considering either {11} partially or {111} partially. Can such string be a part of the language ?
0 votes
0 answers 16 views
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $\text{ has at least as many occurrences of }$ $(000)'$ $\text{s as}$ ... one of the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
0 votes
0 answers 10 views
Given a language $L$, define $L^i$ as follows:$L^0 = \{ \varepsilon \}$$L^i = L^{i-1} \bullet L \text{ for all } I >0$The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____
0 votes
0 answers 8 views
If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$'s in $s$ and $n_1(s)$ the number of $1$'s in $s$. Which one of the following languages is not regular? $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$ ... $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$
0 votes
0 answers 8 views
Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ? $\{\epsilon\}$ $\phi$ $a^*$ $\{\epsilon, a\}$
0 votes
0 answers 8 views
Let $L$ be a regular language. Consider the constructions on $L$ below: $\text{repeat} (L) = \{ww \mid w \in L\}$ $\text{prefix} (L) = \{u \mid \exists v : uv \in L\}$ $\text{suffix} (L) = \{v \mid \exists u: uv \in L\}$ ... of $L$ is best suited to support your answer above? $(a + b)^*$ $\{\epsilon, a, ab, bab\}$ $(ab)^*$ $\{a^nb^n \mid n \geq 0\}$
0 votes
0 answers 6 views
Which of the following languages is regular? $\left\{ww^R \mid w \in \{0, 1\}^+\right\}$ $\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$ $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$ $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$
0 votes
0 answers 11 views
Which of the following is TRUE? Every subset of a regular set is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Infinite union of finite sets is regular
0 votes
0 answers 11 views
Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Context-free, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRUE ? $\overline{L_{3}} \cup L_{4}$ is recursively enumerable. $\overline{L_{2}} \cup L_{3}$ ... -free. $L_{1} \cup \overline{L_{2}}$ is context-free. I only. I and III only. I and IV only. I, II and III only.
0 votes
0 answers 8 views
Which of the following is/are regular languages? $L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w$ $L_2: \left\{ a^nb^m \mid m \neq n \text { and } m, n \geq 0 \right\}$ $L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}$ $L_1$ and $L_3$ only $L_2$ only $L_2$ and $L_3$ only $L_3$ only
0 votes
0 answers 11 views
If $L$ is a regular language over $\Sigma = \{a,b\}$, which one of the following languages is NOT regular? $L.L^R = \{xy \mid x \in L , y^R \in L\}$ $\{ww^R \mid w \in L \}$ $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^*$such that$\ xy \in L\}$ $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^*$such that$\ xy \in L\}$
0 votes
0 answers 9 views
Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$. (For example, let $P$ be the language represented by the regular expression $p^*q^*$ and $Q$ be $\{p^nq^n \mid n \in N\})$. Then which of the following is ALWAYS regular? $P \cap Q$ $P-Q$ $\Sigma^*-P$ $\Sigma^*-Q$
0 votes
0 answers 10 views
Let $L$ be a regular language. Consider the constructions on $L$ below: repeat $(L) = \{ww \mid w \in L\}$ prefix $(L) = \{u \mid ∃v : uv \in L\}$ suffix $(L) = \{v \mid ∃u : uv \in L\}$ half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$ Which of the constructions could lead to a non-regular language? Both I and IV Only I Only IV Both II and III
0 votes
0 answers 9 views
If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$ Which one of the following is CORRECT? Only I Only II Both I and II Neither I nor II
0 votes
0 answers 9 views
Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$ I and IV only I and III only I only IV only
0 votes
0 answers 6 views
Which one of the following is TRUE? The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular. The language $L$ ... $L = \left\{ww \mid w \in \Sigma^* \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.
0 votes
0 answers 10 views
What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states? $L$ must be $\{a^n \mid n \ \text{ is odd}\}$ $L$ must be $\{a^n \mid n \ \text{ is even}\}$ $L$ must be $\{a^n \mid n \geq 0\}$ Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$
0 votes
0 answers 10 views
Language $L_{1}$ is defined by the grammar: $S_{1} \rightarrow a S_{1} b \mid \varepsilon$ Language $L_{2}$ is defined by the grammar: $S_{2} \rightarrow a b S_{2} \mid \varepsilon$ Consider the following statements: P: $L_{1}$ is regular Q: $L_{2}$ is regular Which one of the following ... $Q$ are true. $P$ is true and $Q$ is false. $P$ is false and $Q$ is true. Both $P$ and $Q$ are false.
0 votes
0 answers 8 views
Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$ Which of the languages are regular? Only $L1$ and $L2$ Only $L2, L3$ and $L4$ Only $L3$ and $L4$ Only $L3$
0 votes
0 answers 7 views
Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct? Only $S_1$ is correct Only $S_2$ is correct Both $S_1$ and $S_2$ are correct None of $S_1$ and $S_2$ is correct
0 votes
0 answers 8 views
Which of the following statements about regular languages is NOT true ? Every language has a regular superset Every language has a regular subset Every subset of a regular language is regular Every subset of a finite language is regular
0 votes
0 answers 7 views
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: $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.
0 votes
0 answers 8 views
Which of the following statements is false? Every finite subset of a non-regular set is regular Every subset of a regular set is regular Every finite subset of a regular set is regular The intersection of two regular sets is regular
0 votes
0 answers 10 views
Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n > 0\right\}$ then the languages $L \cup R$ and $R$ are respectively regular, regular not regular, regular regular, not regular not regular, not regular
0 votes
0 answers 5 views
Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$? $abaabaaabaa$ $aaaabaaaa$ $baaaaabaaaab$ $baaaaabaa$ $\text{1, 2 and 3}$ $\text{2, 3 and 4}$ $\text{1, 2 and 4}$ $\text{1, 3 and 4}$
0 votes
0 answers 31 views
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which of the following is the strongest correct statement about a finite language over some finite alphabet $\Sigma$ ? It could be undecidable It is Turing-machine recognizable It is a context sensitive language. It is a regular language. None of the above,
0 votes
0 answers 13 views
Which of the following languages is (are) non-regular? $L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}$ $L_2 = \{w \mid w$ reads the same forward and backward$\}$ $L_3 = \{w \in \{0, 1\} ^* \mid w$ contains an even number of 0's and an even number of 1's$\}$ $L_2$ and $L_3$ only $L_1$ and $L_2$ only $L_3$ only $L_2$ only
0 votes
0 answers 14 views
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the sub string $00$ nor the sub string $11$. Consider the grammar S → aSAb S → ∊ A → bA A → ∊ where $S$, $A$ are non-terminal symbols with $S$ being the ... $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?
0 votes
0 answers 14 views
Given that $A$ is regular and $(A \cup B)$ is regular, does it follow that $B$ is necessarily regular? Justify your answer. Given two finite automata $M1, M2$, outline an algorithm to decide if $L(M1) \subset L(M2)$. (note: strict subset)
0 votes
0 answers 7 views
Let $L \subseteq \Sigma^*$ where $\Sigma = \left\{a,b \right\}$. Which of the following is true? $L = \left\{x \mid x \text{ has an equal number of } a\text{'s and }b\text{'s}\right \}$ is regular $L = \left\{a^nb^n \mid n \geq 1\right \}$ ... $L = \left\{a^mb^n \mid m \geq 1, n \geq 1 \right \}$ is regular
0 votes
0 answers 10 views
Is the language generated by the grammar $G$ regular? If so, give a regular expression for it, else prove otherwise G: $S \rightarrow aB$ $B \rightarrow bC$ $C \rightarrow xB$ $C \rightarrow c$
0 votes
0 answers 13 views
State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.
0 votes
0 answers 8 views
State whether the following statements are TRUE or FALSE: All subsets of regular sets are regular.
0 votes
1 answer 72 views
The language is: binary strings in which the number of 1s is a multiple of the number of 0s; Intuitively, we can say that the language is not-regular. But, this can be formally proved using Myhill-Nerode theorem, as it has infinite number of equivalence classes ... theorem, L is nonregular I don't follow the therefore part - how did they conclude that the strings are in different equivalent class
0 votes
2 answers 42 views
Here ‘w^r’ is the reverse of string ‘w’.