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

asked Jun 8 in Theory of Computation promise 5 points 7 views

5 votes

3 answers 1.2K views

GATE CSE 2021 Set 2 | Question: 9 | Video Solution

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$

asked Feb 18 in Theory of Computation Arjun 257 points 1.2K views

4 votes

1 answer 837 views

GATE CSE 2021 Set 2 | Question: 36 | Video Solution

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

asked Feb 18 in Theory of Computation Arjun 257 points 837 views

0 votes

2 answers 79 views

Testing whether a language is regular or not.
L =. a^i b^2j | i,j>=1 is regular or not ?

L =. a^i b^2j | i,j>=1 is regular or not ?

asked Sep 4, 2020 in Theory of Computation Rsharma29 7 points 79 views

0 votes

1 answer 37 views

self_doubt union of language in toc
What will be the union of L1 U L2 ? L1= {a^n b ^m | n≤m} L2={a^n b^m | n≥m}

What will be the union of L1 U L2 ? L1= {a^n b ^m | n≤m} L2={a^n b^m | n≥m}

asked May 10, 2020 in Theory of Computation nitin21038 2 points 37 views

0 votes

0 answers 165 views

Regular Expression/Language
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 ?

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 ?

asked Apr 25, 2020 in Theory of Computation hridayN 5 points 165 views

0 votes

0 answers 16 views

GATE2014-2-36 Video Solution
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)'$ ... 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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 16 views

0 votes

0 answers 10 views

GATE2018-52 Video Solution
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 ____

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 ____

asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views

0 votes

0 answers 8 views

GATE2006-29 Video Solution
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 \}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 8 views

GATE2013-8 Video Solution
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\}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 8 views

GATE2006-IT-81 Video Solution
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\}$ ... is best suited to support your answer above? $(a + b)^*$ $\{\epsilon, a, ab, bab\}$ $(ab)^*$ $\{a^nb^n \mid n \geq 0\}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 6 views

GATE2007-31 Video Solution
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\}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 6 views

0 votes

0 answers 11 views

GATE2007-7 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 11 views

0 votes

0 answers 11 views

GATE2016-2-18 Video Solution
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}$ ... $L_{1} \cup \overline{L_{2}}$ is context-free. I only. I and III only. I and IV only. I, II and III only.

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.

asked Apr 18, 2020 in Theory of Computation admin 573 points 11 views

0 votes

0 answers 8 views

GATE2015-2-51 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 11 views

GATE2019-7 Video Solution
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\}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 11 views

0 votes

0 answers 9 views

GATE2011-24 Video Solution
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$

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$

asked Apr 18, 2020 in Theory of Computation admin 573 points 9 views

0 votes

0 answers 10 views

GATE2006-IT-80 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views

0 votes

0 answers 9 views

GATE2014-2-15 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 9 views

0 votes

0 answers 9 views

GATE2008-53 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 9 views

0 votes

0 answers 6 views

GATE2014-1-15 Video Solution
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.

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.

asked Apr 18, 2020 in Theory of Computation admin 573 points 6 views

0 votes

0 answers 10 views

GATE2000-2.8 Video Solution
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}\}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views

0 votes

0 answers 10 views

GATE2016-2-17 Video Solution
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 ... $Q$ are true. $P$ is true and $Q$ is false. $P$ is false and $Q$ is true. Both $P$ and $Q$ are false.

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.

asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views

0 votes

0 answers 8 views

GATE2001-2.6 Video Solution
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\}$ ... $L1$ and $L2$ Only $L2, L3$ and $L4$ Only $L3$ and $L4$ Only $L3$

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$

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 7 views

GATE2001-1.4 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 7 views

0 votes

0 answers 8 views

GATE2006-IT-30 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 7 views

GATE1990-3-viii Video Solution
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.

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.

asked Apr 18, 2020 in Theory of Computation admin 573 points 7 views

0 votes

0 answers 8 views

GATE1998-2.6 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

0 answers 10 views

GATE1995-2.24 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views

0 votes

0 answers 5 views

GATE2012-25 Video Solution
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}$

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 5 views

0 votes

0 answers 31 views

GATE1991-03,xiv Video Solution
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,

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,

asked Apr 18, 2020 in Theory of Computation admin 573 points 31 views

0 votes

0 answers 13 views

GATE2008-IT-35 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 13 views

0 votes

0 answers 14 views

GATE2000-7 Video Solution
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 ... $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 14 views

0 votes

0 answers 14 views

GATE1999-6 Video Solution
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)

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)

asked Apr 18, 2020 in Theory of Computation admin 573 points 14 views

0 votes

0 answers 7 views

GATE1996-1.10 Video Solution
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

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

asked Apr 18, 2020 in Theory of Computation admin 573 points 7 views

0 votes

0 answers 10 views

GATE1990-15a Video Solution
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$

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$

asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views

0 votes

0 answers 13 views

GATE1987-2h Video Solution
State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.

State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.

asked Apr 18, 2020 in Theory of Computation admin 573 points 13 views

0 votes

0 answers 8 views

GATE1987-2i Video Solution
State whether the following statements are TRUE or FALSE: All subsets of regular sets are regular.

State whether the following statements are TRUE or FALSE: All subsets of regular sets are regular.

asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views

0 votes

1 answer 72 views

Proof that language is non-regular
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 ... L is nonregular I don't follow the therefore part - how did they conclude that the strings are in different equivalent class

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

asked Dec 21, 2019 in Theory of Computation goxul 647 points 72 views

0 votes

2 answers 42 views

Is this a Regular language or not?
Here ‘w^r’ is the reverse of string ‘w’.

Here ‘w^r’ is the reverse of string ‘w’.

asked Oct 18, 2019 in Theory of Computation luc_Bloodstone 19 points 42 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Log In

Register

Recent Posts

No Recent Blog Comments

Recent questions tagged regular-languages