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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged regularlanguages
0
votes
0
answers
1
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
Boss
(
46.5k
points)

21
views
ullman
theoryofcomputation
regularlanguages
pcp
descriptive
+3
votes
2
answers
2
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.4k
points)

240
views
madeeasytestseries
theoryofcomputation
regularlanguages
0
votes
1
answer
3
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.4k
points)

45
views
theoryofcomputation
regularlanguages
contextfreelanguage
+1
vote
0
answers
4
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
(
399
points)

113
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
5
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
Boss
(
46.5k
points)

12
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
1
answer
6
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
Boss
(
46.5k
points)

11
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
0
answers
7
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
Boss
(
46.5k
points)

10
views
michaelsipser
theoryofcomputation
regularlanguages
contextfreelanguages
0
votes
1
answer
8
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
Boss
(
46.5k
points)

24
views
michaelsipser
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
9
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
Boss
(
46.5k
points)

44
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
10
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
Boss
(
46.5k
points)

21
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
11
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
Boss
(
46.5k
points)

16
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
12
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
Boss
(
46.5k
points)

33
views
michaelsipser
theoryofcomputation
regularlanguages
scarnescut
proof
descriptive
0
votes
0
answers
13
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
Boss
(
46.5k
points)

10
views
michaelsipser
theoryofcomputation
regularlanguages
rotationalclosureoflanguage
descriptive
0
votes
0
answers
14
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
Boss
(
46.5k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
15
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
Boss
(
46.5k
points)

5
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
16
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
Boss
(
46.5k
points)

17
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
17
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
Boss
(
46.5k
points)

25
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
18
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
Boss
(
46.5k
points)

27
views
michaelsipser
theoryofcomputation
regularlanguages
pumpinglemma
proof
descriptive
0
votes
1
answer
19
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
Boss
(
46.5k
points)

41
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
20
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
Boss
(
46.5k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
21
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
Boss
(
46.5k
points)

21
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
22
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
Boss
(
46.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
23
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
Boss
(
46.5k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
24
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
Boss
(
46.5k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
25
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
Boss
(
46.5k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 1 Question 44 (Page No. 90)
Let $B$ and $C$ be languages over $\sum = \{0, 1\}.$ Define $B\overset{1}{\leftarrow} C = \{w\in B$ $\text{for some}$ $y\in C$, $\text{strings}$ $w$ $\text{and}$ $y$ $\text{contain equal numbers of}$ $1’s\}.$ Show that the class of regular languages is closed under the $\overset{1}{\leftarrow}$operation.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 1 Question 43 (Page No. 90)
Let $A$ be any language. Define $\text{DROPOUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\text{DROPOUT(A) = $\{xz xyz\in A$ where $x, ... $\text{Theorem 1.47.}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 1 Question 42 (Page No. 89)
For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of regular languages is closed under shuffle.
asked
Apr 29
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

14
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 1 Question 41 (Page No. 89)
For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language $\text{{$w w = a_{1}b_{1} · · · a_{k}b_{k},$ where $a_{1} · · · a_{k} ∈ A$ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of regular languages is closed under perfect shuffle.
asked
Apr 29
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

9
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
perfectshuffle
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 1 Question 40 (Page No. 89)
Recall that string $x$ is a $\text{prefix}$ of string $y$ if a string $z$ exists where $xz = y,$ and that $x$ is a $\text{proper prefix}$ of $y$ if in addition $x\neq y.$ In each of the following parts, we define an operation on a ... $\text{NOEXTEND(A) = {w ∈ A w is not the proper prefix of any string in A}.}$
asked
Apr 28
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

31
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
prefix
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
GATE 2020 Application Form Opened!
My GATE Preparation Journey
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Follow @csegate
Recent questions tagged regularlanguages
Recent Blog Comments
will pdfs be uploaded ?
6th...
Sir
4th...
49,984
questions
55,135
answers
190,487
comments
85,110
users