The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged regularlanguages
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 5 Question 4 (Page No. 239)
If $A \leq_{m} B$ and $B$ is a regular language, does that imply that $A$ is a regular language? Why or why not?
asked
Oct 19
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

2
views
michaelsipser
theoryofcomputation
regularlanguages
reduction
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.
asked
Oct 12
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

7
views
michaelsipser
theoryofcomputation
regularlanguages
proof
+1
vote
1
answer
3
CMI2019A1
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not contextfree contextfree, but not regular both regular and contextfree neither regular nor contextfree
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

94
views
cmi2019
regularlanguages
contextfreelanguage
closureproperty
0
votes
1
answer
4
CMI2019B1
Consider an alphabet $\Sigma=\{a,b\}.$ Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}b.$ Define $L:=\{u\in\Sigma^{\ast}\mid \exists w\in L_{2}\: s.t.\: uw\in L_{1}\}.$ Give an example of a word in $L.$ Give an example of a word not in $L.$ Construct an NFA for $L.$
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

31
views
cmi2019
regularexpressions
regularlanguages
nfa
+1
vote
2
answers
5
CMI2018A1
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

48
views
cmi2018
regularlanguages
regularexpressions
easy
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 9.5 Question 2 (Page No. 418)
Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the instance $(A,B)$ of PCP has no ... homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.
asked
Jul 26
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

34
views
ullman
theoryofcomputation
regularlanguages
pcp
descriptive
+3
votes
2
answers
7
MadeEasy Test Series: Theory Of Computation  Regular Languages
Consider the following statements: $S_1:\{(a^n)^mn\leq m\geq0\}$ $S_2:\{a^nb^nn\geq 1\} \cup \{a^nb^mn \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
asked
May 26
in
Theory of Computation
by
Hirak
Active
(
3.5k
points)

281
views
madeeasytestseries
theoryofcomputation
regularlanguages
0
votes
1
answer
8
self doubt: TOC
is union of regular language and context free language always regular?
asked
May 22
in
Theory of Computation
by
Hirak
Active
(
3.5k
points)

54
views
theoryofcomputation
regularlanguages
contextfreelanguage
+1
vote
0
answers
9
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
asked
May 10
in
Theory of Computation
by
logan1x
Junior
(
887
points)

122
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 2 Question 20 (Page No. 156)
Let $A/B = \{w\mid wx\in A$ $\text{for some}$ $x \in B\}.$ Show that if $A$ is context free and $B$ is regular$,$ then $A/B$ is context free$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

17
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
1
answer
11
Michael Sipser Edition 3 Exercise 2 Question 18 (Page No. 156)
Let $C$ be a contextfree language and $R$ be a regular language$.$ Prove that the language $C\cap R$ is contextfree. Let $A = \{w\mid w\in \{a, b, c\}^{*}$ $\text{and}$ $w$ $\text{contains equal numbers of}$ $a’s, b’s,$ $\text{and}$ $c’s\}.$ Use $\text{part (a)}$ to show that $A$ is not a CFL$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

14
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 2 Question 17 (Page No. 156)
Use the results of $\text{Question 16}$ to give another proof that every regular language is context free$,$ by showing how to convert a regular expression directly to an equivalent contextfree grammar$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

11
views
michaelsipser
theoryofcomputation
regularlanguages
contextfreelanguages
0
votes
1
answer
13
Michael Sipser Edition 3 Exercise 2 Question 13 (Page No. 156)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ $U\rightarrow 0U00\mid\#$ Describe $L(G)$ in English. Prove that $L(G)$ is not regular$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

27
views
michaelsipser
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $s < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $s < k1k2.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

49
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
15
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

29
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
16
Michael Sipser Edition 3 Exercise 1 Question 70 (Page No. 93)
We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove that the class of regular languages is closed under the ${avoids}$ operation.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

24
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 1 Question 68 (Page No. 93)
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex cut, called $\text{Scarne's cut,}$ the deck is broken into three parts ... $ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

40
views
michaelsipser
theoryofcomputation
regularlanguages
scarnescut
proof
descriptive
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 1 Question 67 (Page No. 93)
Let the rotational closure of language $A$ be $RC(A) = \{yx xy ∈ A\}.$ Show that for any language $A,$ we have $RC(A) = RC(RC(A)).$ Show that the class of regular languages is closed under rotational closure.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

14
views
michaelsipser
theoryofcomputation
regularlanguages
rotationalclosureoflanguage
descriptive
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 1 Question 63 (Page No. 92)
Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets. Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if $B\subseteq D$ and $D$ contains infinitely many ... regular languages where $B\subseteqq D,$ then we can find a regular language $C$ where $B\subseteqq C\subseteqq D.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 1 Question 58 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that $A_{\frac{1}{2}\frac{1}{3}}=\{\text{xzfor some y,x=y=z and xyz $\in$ A\}}.$ Show that if $A$ is regular,then $A_{\frac{1}{2}\frac{1}{3}}$ is not necessarily regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

9
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 1 Question 57 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}}=\{\text{xfor some y,x=y and xy $\in$ A\}}.$ Show that if $A$ is regular,then so is $A_{\frac{1}{2}}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

21
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 1 Question 56 (Page No. 91)
If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w w is the representation in base k of some number in A\}}.$ Here, we do not allow leading $0's$ in the representation of a ... a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular$.$ Prove that your example works.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

27
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
23
Michael Sipser Edition 3 Exercise 1 Question 55 (Page No. 91)
The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is a pumping length for language $A,$ so is any length $p^{'}\geq p.$ The minimum pumping ... $\epsilon$ $1^{*}01^{*}01^{*}$ $10(11^{*}0)^{*}0$ $1011$ $\sum^{*}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

46
views
michaelsipser
theoryofcomputation
regularlanguages
pumpinglemma
proof
descriptive
0
votes
1
answer
24
Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)
Consider the language $F=\{a^{i}b^{j}c^{k}i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$ Show that $F$ is not regular. Show that $F$ acts like a regular language in the pumping lemma. ... three conditions of the pumping lemma for this value of $p.$ Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

49
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+zx,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
26
Michael Sipser Edition 3 Exercise 1 Question 49 (Page No. 90)
Let $B=\{1^{k}yy\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}yy\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

23
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 1 Question 48 (Page No. 90)
Let $\sum = \{0,1\}$ and let $D = \{ww$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$ Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

11
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 1 Question 47 (Page No. 90)
Let $\sum=\{1,\#\}$ and let $Y=\{ww=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 1 Question 46 (Page No. 90)
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}m,n\geq 0\}$ $\{0^{m}1^{n}m\neq n\}$ $\{ww\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtww,t\in\{0,1\}^{+}\}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

19
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 1 Question 45 (Page No. 90)
Let $\text{A/B = {w wx ∈ A for some x ∈ B}}.$ Show that if $A$ is regular and $B$ is any language, then $\text{A/B}$ is regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

9
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
Page:
1
2
3
4
5
6
...
20
next »
Quick search syntax
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
Recent Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged regularlanguages
Recent Blog Comments
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
50,647
questions
56,504
answers
195,502
comments
100,864
users