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

3 votes

2 answers

661

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

748 views

shreshtha5 asked Dec 5, 2015

11 votes

2 answers

662

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

2 votes

3 answers

663

Identify the language accepted by the following NFA with $\in$-moves.
Identify the language accepted by the following NFA with $\in$-moves. All strings over a's and b's All strings which do not contain aa All strings which do not contain bb None of these ----- ... words instead of precise notation , makes this question confusing. Please answer this question, what should be correct answer.

Identify the language accepted by the following NFA with $\in$-moves.All strings over a's and b'sAll strings which do not contain aaAll strings which do not contain bbNon...

Akash Kanase

1.3k views

Akash Kanase asked Dec 1, 2015

3 votes

2 answers

664

if $w \in (a+b)^*$ satisfies $abw = wab$, then $\text{length}(w)$ is ?

monali

1.7k views

monali asked Nov 24, 2015

22 votes

3 answers

665

TIFR CSE 2014 | Part B | Question: 12
Consider the following three statements: Intersection of infinitely many regular languages must be regular. Every subset of a regular language is regular. If $L$ is regular and $M$ is not regular then $L ∙ M$ is necessarily not regular. Which of the ... above? true, false, true. false, false, true. true, false, true. false, false, false. true, true, true.

Consider the following three statements:Intersection of infinitely many regular languages must be regular.Every subset of a regular language is regular.If $L$ is regular ...

makhdoom ghaya

4.9k views

makhdoom ghaya asked Nov 20, 2015

19 votes

3 answers

666

TIFR CSE 2013 | Part B | Question: 8
Which one of the following languages over the alphabet ${0, 1}$ is regular? The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively. The language of palindromes, i.e. bit strings $x$ that read the same from left to right as well as right to ... $(c)$ above. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$

Which one of the following languages over the alphabet ${0, 1}$ is regular?The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively.The lang...

makhdoom ghaya

4.1k views

makhdoom ghaya asked Nov 6, 2015

27 votes

2 answers

667

TIFR CSE 2013 | Part B | Question: 6
Let $L$ and $L'$ be languages over the alphabet $\Sigma $. The left quotient of $L$ by $L'$ is $L/L'\overset{{def}}{=} \left\{w \in \Sigma^* : wx ∈ L\text{ for some }x \in L'\right\}$ ... then $L$ is regular. $L/L'$ is a subset of $L$. If $L/L'$ and $L'$ are regular, then $L$ is regular.

Let $L$ and $L'$ be languages over the alphabet $\Sigma $. The left quotient of $L$ by $L'$ is$L/L'\overset{{def}}{=} \left\{w \in \Sigma^* : wx ∈ L\text{ for some }x \...

makhdoom ghaya

3.0k views

makhdoom ghaya asked Nov 6, 2015

3 votes

2 answers

668

Choose the regular set.
Choose the regular set $\left\{ww^{R}ww^{R}ww \mid w \in \{a,b \}^+ \right\}$ $\left\{ a^{2^n} a^{n!}a^{pq} \mid p \text{ prime}, q\text{ not prime}, n \geq1\right\}$ $\left\{ wXw^{R} \mid w, X \in \{a,b \}^+ \right\}$ $\left\{a^{i}b^{j}a^{i}b^{j}a^{i}b^{j} \mid i,j \geq 1 \right\}$

Choose the regular set$\left\{ww^{R}ww^{R}ww \mid w \in \{a,b \}^+ \right\}$$\left\{ a^{2^n} a^{n!}a^{pq} \mid p \text{ prime}, q\text{ not prime}, n \geq1\right\}$$\lef...

अनुराग पाण्डेय

619 views

अनुराग पाण्डेय asked Nov 5, 2015

3 votes

0 answers

669

What should be answers of Question 14, 15 and 16 and Why ??
Common Data for Q14,15 &16 is given below: Ram takes two context-free languages $L_1$ and $L_2$ a). He concatenates $L_1 $ and $L_2$ to obtain a new set $L_3$. b). He takes the complement of $L_3$ to obtain a set $L_4$ c). ... is a). recursive b). csl that is not finite c). cfl that may regular d). r.e. set that is never finite.

Common Data for Q14,15 &16 is given below: Ram takes two context-free languages $L_1$ and $L_2$ a). He concatenates $L_1 $ and $L_2$ to obtain a new set $L_3$.b). He take...

Payal Rastogi

593 views

Payal Rastogi asked Nov 2, 2015

2 votes

2 answers

670

Which of these is/are CFGs

Mojo-Jojo

446 views

Mojo-Jojo asked Sep 29, 2015

3 votes

3 answers

671

Regular Language
Is $\{xww \mid w,x \in (a+b)^{+}\}$ regular because there is no restriction on the max length of $x$ ? As mush as I know, if there is no restriction on the maximum value of $x$, then it can expand as much as to cover $ww$, making the language regular. Please correct me if I am wrong.

Is $\{xww \mid w,x \in (a+b)^{+}\}$ regular because there is no restriction on the max length of $x$ ?As mush as I know, if there is no restriction on the maximum value o...

Mojo-Jojo

1.3k views

Mojo-Jojo asked Sep 29, 2015

2 votes

2 answers

672

Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ?
Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ? Does this imply that a subset of non regular language can be regular ?

Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ?Does this imply that a subset of non regular language can be regular ?

Mojo-Jojo

1.2k views

Mojo-Jojo asked Sep 28, 2015

1 votes

2 answers

673

Is this language regular?
Is L={0, 011, 011000, 0110001111, ....} a regular language? I know that the language should follow some regular pattern and we should be able to construct a regex for it in order to say it a RL. Morever it shouldnt require any kind of extra ... wud be thankful if somebody suggests a quick method to identify given set to be RL or NRL based on pattern. Thanks in advance :)

Is L={0, 011, 011000, 0110001111, ....} a regular language?I know that the language should follow some regular pattern and we should be able to construct a regex for it i...

Tushar Shinde

859 views

Tushar Shinde asked Sep 15, 2015

6 votes

2 answers

674

equal number of sequence, is language regular ?
L1= Set of all strings having equal number of 00 and 11. L2= Set of all strings having equal number of 01 and 10. (a) Both are Regular (b) Both are Context-Free (c) L1 is regular, L2 is Context Free (d) L1 is CF, L2 is Regular

L1= Set of all strings having equal number of 00 and 11.L2= Set of all strings having equal number of 01 and 10.(a) Both are Regular (b) Both are Context-Free(c) L1 is re...

Deepak Sharma 1

6.6k views

Deepak Sharma 1 asked Aug 18, 2015

4 votes

2 answers

675

Equivalence classes of a Language
Find all the equivalence classes of Regular Language 011 (0+1)* 011

Find all the equivalence classes of Regular Language011 (0+1)* 011

praj

4.4k views

praj asked Aug 18, 2015

2 votes

1 answer

676

Is this language regular?
$L = \{ a^{n}b^{m} \mid (n+m) \text{ is even}\}$

$L = \{ a^{n}b^{m} \mid (n+m) \text{ is even}\}$

Shefali

304 views

Shefali asked Aug 14, 2015

0 votes

1 answer

677

Which of the following statements is/are True?
(a) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is regular. (b) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is non-regular.

(a) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is regular.(b) If $R$ is regular and $N$ is non-regular, then there exists $R+N$, which is no...

Shefali

1.6k views

Shefali asked Aug 14, 2015

6 votes

7 answers

678

UGC NET CSE | December 2014 | Part 3 | Question: 24
Regular expression for the complement of language $L=\left\{a^{n}b^{m} \mid n \geq 4, m \leq 3\right\}$ is $(a + b)^{*} ba(a + b)^{*}$ $a^{*} bbbbb^{*}$ $(\lambda + a + aa + aaa)b^{*} + (a + b)^{*} ba(a + b)^{*}$ None of the above

Regular expression for the complement of language $L=\left\{a^{n}b^{m} \mid n \geq 4, m \leq 3\right\}$ is $(a + b)^{*} ba(a + b)^{*}$ $a^{*} bbbbb^{*}$ $(\lambda + a + a...

Vivek sharma

11.0k views

Vivek sharma asked Jul 17, 2015

1 votes

4 answers

679

If a Finite state machine that accepts a set, has no loop...eg: accepts only 101. Is it the set regular? does it have the PUMPING LEMMA property?(If it is regular but has no loops)

Lord bendtner

624 views

Lord bendtner asked Jun 6, 2015

30 votes

3 answers

680

GATE CSE 2015 Set 2 | Question: 51
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...

go_editor

11.2k views

go_editor asked Feb 13, 2015

3 votes

1 answer

681

which of the following is always regular
Let P be a regular language and Q be a context free language such that Q ⊂ P. Which of the following is always regular ? (A) P ∩ Q (B) P-Q (C) Σ* - P (D) Σ* - Q

Let P be a regular language and Q be a context free language such that Q ⊂ P.Which of the following is always regular ?(A) P ∩ Q(B) P-Q(C) Σ* - P(D) Σ* - Q

ASHU2015

661 views

ASHU2015 asked Dec 11, 2014

5 votes

3 answers

682

L is regular or not??
Let $\sum$ = {a, b} and Let L = { w | w contains an equal no of occurrences of substring 'ab' and 'ba' }. Thus aba $\in$ L since 'aba' contains one occurrence of 'ab' and one occurence of 'ba' but abab $\notin$ L. ... A. L is regular. B. L is DCFL but not regular. C. L is CFL but not regular. D. L is recursive but not a CFL.

Let $\sum$ = {a, b} and Let L = { w | w contains an equal no of occurrences of substring 'ab' and 'ba' }. Thus aba $\in$ L since 'aba' contains one occurrence of 'ab' and...

Isha Karn

999 views

Isha Karn asked Nov 18, 2014

14 votes

1 answer

683

Given that a language LA = L1 U L2,
Given that a language $L_A = L_1 \cup L_2$, where $L_1$ and $L_2$ are two other languages. If $L_A$ is known to be a regular language, then which of the following statements is necessarily TRUE? If $L_1$ is regular then $L_2$ will also be ... finite then $L_2$ will be regular If $L_1$ is regular and finite then $L_2$ will also be regular and finite None of these

Given that a language $L_A = L_1 \cup L_2$, where $L_1$ and $L_2$ are two other languages. If $L_A$ is known to be a regular language, then which of the following stateme...

Arjun

4.7k views

Arjun asked Nov 4, 2014

41 votes

4 answers

684

GATE IT 2006 | Question: 81
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\}$$\tex...

Ishrat Jahan

11.2k views

Ishrat Jahan asked Nov 1, 2014

31 votes

2 answers

685

GATE IT 2006 | Question: 80
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...

Ishrat Jahan

9.4k views

Ishrat Jahan asked Nov 1, 2014

29 votes

1 answer

686

GATE IT 2006 | Question: 30
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 supersetEvery language has a regular subsetEvery subset of a regular l...

Ishrat Jahan

8.0k views

Ishrat Jahan asked Oct 31, 2014

34 votes

2 answers

687

GATE CSE 2011 | Question: 24
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...

akash

9.9k views

akash asked Oct 29, 2014

28 votes

3 answers

688

GATE IT 2008 | Question: 35
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 = ...

Ishrat Jahan

7.3k views

Ishrat Jahan asked Oct 28, 2014

1 votes

1 answer

689

Regular or not ?
{ wxw | w belongs to {0,1}* , x belongs to {0,1}+ }

{ wxw | w belongs to {0,1}* , x belongs to {0,1}+ }

Isha Karn

1.9k views

Isha Karn asked Oct 25, 2014

12 votes

2 answers

690

proof regarding infinite union/intesection
Q1:Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices). Ans1: Consider the sets {0}, {01}, {0011}, etc. Each one is regular because it only contains one string. But the infinite ... regularity. Please explain what is infinite union/ infinite intersection and also explain the answer This question is from aduni.org

Q1:Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices).Ans1: Consider the sets {0}, {01}, {0011}, etc. Each one is regular because it...

Aravind

12.6k views

Aravind asked Oct 21, 2014

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