Recent questions tagged regular-language / GATE Overflow for GATE CSE

5 votes

4 answers

631

ISI2015-PCB-CS-5a
Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular. Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 \cup L_2$ is regular.

Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular.Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 ...

go_editor

1.8k views

go_editor asked May 30, 2016

1 votes

1 answer

632

CMI2011-B-04b
Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\}^* \mid \text{ reverse}(w) \in L \}$ - here $reverse(w)$ denotes the ... where $x=yz, \: y \in L, \: z \in L^R \}$ is regular. How can you use $N$ to construct an automata for $L.L^R$?

Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the l...

go_editor

486 views

go_editor asked May 27, 2016

13 votes

3 answers

633

CMI2015-A-09
Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true: If $L_2$ is regular, then $L_1$ must also be regular. If $L_1$ is regular, then $L_2$ must also be regular. Either both $L_1$ and $L_2$ are regular, or both are not regular. None of the above.

Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true:If $L_2$ is regular, then $L_1$ must also be regu...

go_editor

1.2k views

go_editor asked May 27, 2016

1 votes

2 answers

634

CMI2014-B-01
Let $A$ be a regular language. Consider the following operations on $A$: $2A:=\{xy \mid x, \: y \in A \text{ and } x=y\}$ $A^2 :=\{xy \mid x, \: y \in A\}$ One of these operations necessarily leads to a regular language and the ... that it is regular. For the non-regular operation, give an example of an $A$ such that applying the operation on it results in a non-regular language.

Let $A$ be a regular language. Consider the following operations on $A$:$2A:=\{xy \mid x, \: y \in A \text{ and } x=y\}$$A^2 :=\{xy \mid x, \: y \in A\}$One of these oper...

go_editor

825 views

go_editor asked May 27, 2016

1 votes

0 answers

635

Regular and Non Regular set
Consider the following subsets of {a,b,S}* A={xy| x,y∊{a,b}* , #a(x)=#b(y)} B={xSy| x,y∊{a,b}* , #a(x)=#b(y)} {where S=$} Which of the following statements are true ? (A) A and B are both regular (B) A is regular but B is not (C) A is not regular but B is regular (D) Both are non-regular

Consider the following subsets of {a,b,S}*A={xy| x,y∊{a,b}* , #a(x)=#b(y)}B={xSy| x,y∊{a,b}* , #a(x)=#b(y)}{where S=$}Which of the following statements are true ?(A) ...

biranchi

1.1k views

biranchi asked May 24, 2016

19 votes

3 answers

636

CMI2012-A-01
Let $L \subseteq \{0,1\}^*$. Which of the following is true? If $L$ is regular, all subsets of $L$ are regular. If all proper subsets of $L$ are regular, then $L$ is regular. If all finite subsets of $L$ are regular, then $L$ is regular. If a proper subset of $L$ is not regular, then $L$ is not regular.

Let $L \subseteq \{0,1\}^*$. Which of the following is true?If $L$ is regular, all subsets of $L$ are regular.If all proper subsets of $L$ are regular, then $L$ is regula...

go_editor

5.8k views

go_editor asked May 22, 2016

1 votes

1 answer

637

CMI2011-B-04a
Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\} | \text{ reverse}(w) \in L \}$ ... reverse. For example $reverse(0001) = 1000$. Show that $L^R$ is regular, How can you use $N$ to construct an automata to recognize $L^R$.

Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the lan...

go_editor

516 views

go_editor asked May 19, 2016

1 votes

1 answer

638

CMI2011-A-01
Let L $\subseteq \{0, 1\}^&lowast;$ be a language accepted by a finite automaton. Let $F$ be some subset of $\{0, 1\}^&lowast;$, containing 2011 strings. Which of the following statements is true? Justify your answer. $L \: \: \cup \:\: F$ ... . $L \: \cup \: F$ is never regular. $L \: \cup \: F$ is regular only if $L$ contains $\in$ (the empty string).

Let L $\subseteq \{0, 1\}^&lowast;$ be a language accepted by a finite automaton. Let $F$ be some subset of $\{0, 1\}^&lowast;$, containing 2011 strings. Which of the fol...

go_editor

904 views

go_editor asked May 19, 2016

1 votes

1 answer

639

Why a^n / n is odd (even) is regular Language ?
How could we construct a FA by finding out a pattern in this language if we take n is odd then we consider n=1 ,3 ,5 ,7 (here string is in AP so we would be able to find out FA) it is okay but it it not said that we should ... but now there is no pattern now how can we construct a FA ).... can someone explain this ? Assume same for if n is even.

How could we construct a FA by finding out a pattern in this language if we take n is odd then we consider n=1 ,3 ,5 ,7 (here string is in AP so we would be able to find...

shekhar chauhan

1.9k views

shekhar chauhan asked May 10, 2016

3 votes

1 answer

640

find all strings in ((a+b)*b(a+ab)*) of length less then 4.

shekhar chauhan

5.5k views

shekhar chauhan asked Apr 19, 2016

2 votes

5 answers

641

Why is (a + b)* a regular language?
The language (a+b)* is regular as there is a regular expression for it.But this language contains all possible strings. So it should imply that regular language is the super-set of all languages, but clearly it isn't! Subsets like $a^{n}b^{n}$ are not regular. Can someone tell me what am I missing?

The language (a+b)* is regular as there is a regular expression for it.But this language contains all possible strings. So it should imply that regular language is the su...

Neelay Upadhyaya

3.0k views

Neelay Upadhyaya asked Apr 16, 2016

48 votes

2 answers

642

GATE CSE 2016 Set 2 | Question: 18
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 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 TRU...

Akash Kanase

12.1k views

Akash Kanase asked Feb 12, 2016

22 votes

2 answers

643

GATE CSE 2016 Set 2 | Question: 17
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 \v...

Akash Kanase

7.8k views

Akash Kanase asked Feb 12, 2016

0 votes

0 answers

644

Determine the type of language

Sourasekhar Banerjee

475 views

Sourasekhar Banerjee asked Feb 12, 2016

3 votes

1 answer

645

regular language
Let L1,L2 be two arbitarily language then state true or false-: please give proper explanation... 1)if L1.L2 is regular then is L1,L2 regular too? 2) if L1.L2 is regular then is L2.L1 is regular too?

Let L1,L2 be two arbitarily language then state true or false-:please give proper explanation...1)if L1.L2 is regular then is L1,L2 regular too?2) if L1.L2 is regular the...

sourav.

987 views

sourav. asked Feb 3, 2016

5 votes

1 answer

646

Whether w wr x where w,x belongs to {a,b}* Regular?
$L = \{ww_rx, \text{ where } w,x \in \{a,b\}^*\}$ is definitely regular $w$ can always be considered to be empty string $(\epsilon).$ So, this just becomes $(a+b)^*$ language. What about the following one? Whether $L=\{ww_rx, \text{ where } w,x \in \{a,b\}^+\}$ regular?

$L = \{ww_rx, \text{ where } w,x \in \{a,b\}^*\}$ is definitely regular $w$ can always be considered to be empty string $(\epsilon).$ So, this just becomes $(a+b)^*$ lang...

Anshul Khantwal

2.1k views

Anshul Khantwal asked Jan 30, 2016

5 votes

4 answers

647

If L1 is Regular, and L1UL2 is regular, then L2 is?
Consider L1, L2 ⊆ Ʃ* such that L1 and L1 ∪ L2 are regular. (a) L2 is definitely regular (b) L2 may not be regular (c) L2 is context free (d) None of above Is it option B or C? How?

Consider L1, L2 ⊆ Ʃ* such that L1 and L1 ∪ L2 are regular.(a) L2 is definitely regular(b) L2 may not be regular(c) L2 is context free(d) None of aboveIs it option B ...

Purple

8.8k views

Purple asked Jan 28, 2016

4 votes

2 answers

648

MadeEasy Test Series: Theory Of Computation - Regular Languages
Which of the following grammars generate regular language? a. S $\rightarrow$ aSa | bSb | a b. S $\rightarrow$ aS | bS | aA | bA A $\rightarrow$ bAc | $\epsilon$ c. S $\rightarrow$ aA | $\epsilon$ A $\rightarrow$ Sb d. None of these Why (A) is not regular? as {WCW^r | W,C belongs to (a,b)} is regular}

Which of the following grammars generate regular language?a. S $\rightarrow$ aSa | bSb | a b. S $\rightarrow$ aS | bS | aA | bA A $\rightarrow$ bAc | $\epsilon$c. S $\...

Tushar Shinde

1.3k views

Tushar Shinde asked Jan 25, 2016

0 votes

0 answers

649

CFG regular or NOT
How to identify regular CFG

How to identify regular CFG

Pradip Nichite

342 views

Pradip Nichite asked Jan 21, 2016

2 votes

2 answers

650

which of these are regular sets ?
$L_1=\left\{a^pb^q \mid p+q \geq10^6 \right\}$ $L_2=\left\{a^mb^n \mid m-n \geq 10^6\right\}$ In both of these there is a comparison between no of a's and b's so I guess both of them should be non-regular sets but why only L2 is non-regular ?

$L_1=\left\{a^pb^q \mid p+q \geq10^6 \right\}$$L_2=\left\{a^mb^n \mid m-n \geq 10^6\right\}$In both of these there is a comparison between no of a's and b's so I guess bo...

radha gogia

716 views

radha gogia asked Jan 14, 2016

0 votes

0 answers

651

Homomorphishm operation
If ∑={0,1} ∆={a,b} and h(0)=aa h(1)=bb And L={ab+ba}* then what is h(h-1(L)) ? I knw here h-1(L) is ∅(phi).

If ∑={0,1} ∆={a,b} and h(0)=aa h(1)=bbAnd L={ab+ba}*then what is h(h-1(L)) ?I knw here h-1(L) is ∅(phi).

khushtak

285 views

khushtak asked Jan 13, 2016

0 votes

2 answers

652

transition diagram for the given regular language
L={wxwr∣ w,x∈(a,b)*} Is this language regular language? Plz give transition diagram or table?

L={wxwr∣ w,x∈(a,b)*}Is this language regular language?Plz give transition diagram or table?

khushtak

569 views

khushtak asked Jan 12, 2016

1 votes

1 answer

653

REGULAR EXPRESSION - Inverse homomorphism
Let r = (10 + 0) * 11(0 + 1) * be a regular expression for the regular language L and let h(0) = ab and h(1) = ba a homomorphism. What is a regular expression for h(L)? How about h −1 (L′) if L′ is given by the regular expression r ′ = (ab + a) * bb(a + b) *?

Let r = (10 + 0) * 11(0 + 1) * be a regular expression for the regular language L and let h(0) = ab and h(1) = ba a homomorphism. What is a regular expression for h(L)? H...

bahirNaik

746 views

bahirNaik asked Jan 4, 2016

12 votes

1 answer

654

Why this is not a regular language?
Consider following languages : L1 = { wxwy | x,w,y $\in$(a + b)+ } , L2 = { xwyw | x,w,y $\in$(a + b)+ } , L3 = { wxyw | x, y, w $\in$(a+b)+ } How can we say that L1 , L2 are regular but not L3 ? Please explain.

Consider following languages :L1 = { wxwy | x,w,y $\in$(a + b)+ } ,L2 = { xwyw | x,w,y $\in$(a + b)+ } ,L3 = { wxyw | x, y, w $\in$(a+b)+ } How can we say that L1 , L2 ar...

Utk

2.2k views

Utk asked Dec 30, 2015

1 votes

3 answers

655

Subset of a Regular Expression
Consider the regular expression $R=(a+b)^*a(ab)^*+\epsilon$. Which of the following are possible as subset of $R$? (i) $(aa)^*$ (ii) $(ba)^*$ (iii) $(aa)^*(ba)^*$ a. $(i)$ and $(ii)$ only b. $(ii)$ and $(iii)$ only c. $(i)$,$(ii)$ and $(iii)$ d. None of these.

Consider the regular expression $R=(a+b)^*a(ab)^*+\epsilon$.Which of the following are possible as subset of $R$?(i) $(aa)^*$ (ii) $(ba)^*$ (iii) $(aa)^...

Akanksha Kesarwani

1.2k views

Akanksha Kesarwani asked Dec 13, 2015

21 votes

2 answers

656

TIFR CSE 2015 | Part B | Question: 10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.

Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wed...

makhdoom ghaya

2.9k views

makhdoom ghaya asked Dec 8, 2015

15 votes

3 answers

657

TIFR CSE 2015 | Part B | Question: 6
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic ... not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.

Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$.$B$ can be recognized by a deterministic finite state...

makhdoom ghaya

2.0k views

makhdoom ghaya asked Dec 7, 2015

13 votes

4 answers

658

VirtualGate Test Series: Theory Of Computation - Regular Languages
Consider the following subsets of $\left\{a, b, \$ \right\}^*$ $A=\left\{xy\, |\, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\},$ $ ... are true? $A$ and $B$ both are regular $A$ is regular but $B$ is not $A$ is not regular but $B$ is regular Both are non-regular

Consider the following subsets of $\left\{a, b, \$ \right\}^*$$A=\left\{xy\, |\, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\},$$B=\left\{x\$y\, |\, x,y\in\left\{a,b\r...

shreshtha5

1.6k views

shreshtha5 asked Dec 5, 2015

3 votes

2 answers

659

Regular/Non-regular Language
Given a set $A\subseteq \left\{0,1 \right \}^*,$ let $A' = \left\{ xy\; |\;x1y\in A\right\}.$ That is, $A'$ consistes of all the strings obtained from a string in $A$ by deleting in $A$ by deleting exactly one $1$. if $A$ is regular, then $A'$ is (A) Regular (B) Context free but not regular (C) Recursive but not context free (D) None of the above.

Given a set $A\subseteq \left\{0,1 \right \}^*,$ let$A' = \left\{ xy\; |\;x1y\in A\right\}.$ That is, $A'$ consistes of all the strings obtained from a string in $A$ by d...

shreshtha5

741 views

shreshtha5 asked Dec 5, 2015

11 votes

2 answers

660

LL(1) expressive power
Does there exist LL(1) grammar for every Regular Language ? OR For Every Regular Language there exist atleast one LL(1) Grammar . True /False

Does there exist LL(1) grammar for every Regular Language ? ORFor Every Regular Language there exist atleast one LL(1) Grammar . True /False

Himanshu1

3.1k views

Himanshu1 asked Dec 5, 2015

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