The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
1
answer
1
UGCNETJan2017III: 19
Which of the following are not regular? Strings of even number of a’s Strings of a’s , whose length is a prime number. Set of all palindromes made up of a’s and b’s. Strings of a’s whose length is a perfect square. (a) and (b) only (a), (b) and (c) only (b),(c) and (d) only (b) and (d) only
asked
Mar 24
in
Theory of Computation
by
jothee

61
views
ugcnetjan2017iii
theoryofcomputation
regularlanguages
0
votes
2
answers
2
UGCNETJan2017III: 20
Consider the languages $L_{1}= \phi$ and $L_{2}=\{1\}$. Which one of the following represents $L_{1}^{\ast}\cup L_{2}^{\ast} L_{1}^{\ast}$? $\{\in \}$ $\{\in,1\}$ $\phi$ $1^{\ast}$
asked
Mar 24
in
Theory of Computation
by
jothee

70
views
ugcnetjan2017iii
theoryofcomputation
regularlanguages
0
votes
2
answers
3
UGCNETJan2017III: 21
Given the following statements: A class of languages that is closed under union and complementation has to be closed under intersection A class of languages that is closed under union and intersection has to be closed under complementation Which of the following options is correct? Both (a) and ... Both (a) and (b) are true (a) is true, (b) is false (a) is false, (b) is true
asked
Mar 24
in
Theory of Computation
by
jothee

58
views
ugcnetjan2017iii
theoryofcomputation
regularlanguages
+2
votes
2
answers
4
ISRO202038
Which of the following is true? Every subset of a regular set is regular Every finite subset of nonregular set is regular The union of two non regular set is not regular Infinite union of finite set is regular
asked
Jan 14
in
Theory of Computation
by
Satbir

221
views
isro2020
theoryofcomputation
regularlanguages
easy
0
votes
0
answers
5
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

18
views
michaelsipser
theoryofcomputation
regularlanguages
reduction
proof
0
votes
0
answers
6
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 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

15
views
michaelsipser
theoryofcomputation
regularlanguages
proof
+1
vote
1
answer
7
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 14, 2019
in
Theory of Computation
by
gatecse

171
views
cmi2019
regularlanguages
contextfreelanguages
closureproperty
0
votes
1
answer
8
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 14, 2019
in
Theory of Computation
by
gatecse

127
views
cmi2019
regularexpressions
regularlanguages
nfadfa
+2
votes
3
answers
9
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 14, 2019
in
Theory of Computation
by
gatecse

201
views
cmi2018
regularlanguages
regularexpressions
easy
0
votes
0
answers
10
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 27, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

59
views
ullman
theoryofcomputation
regularlanguages
pcp
descriptive
+3
votes
2
answers
11
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, 2019
in
Theory of Computation
by
Hirak

439
views
madeeasytestseries
theoryofcomputation
regularlanguages
0
votes
1
answer
12
self doubt: TOC
is union of regular language and context free language always regular?
asked
May 23, 2019
in
Theory of Computation
by
Hirak

80
views
theoryofcomputation
regularlanguages
contextfreelanguages
+2
votes
0
answers
13
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
asked
May 10, 2019
in
Theory of Computation
by
logan1x

197
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguages
context
0
votes
0
answers
14
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

32
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
1
answer
15
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
0
answers
16
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

22
views
michaelsipser
theoryofcomputation
regularlanguages
contextfreelanguages
0
votes
1
answer
17
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

51
views
michaelsipser
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
18
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

77
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
19
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

76
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
20
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

77
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
21
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

82
views
michaelsipser
theoryofcomputation
regularlanguages
scarnescut
proof
descriptive
0
votes
0
answers
22
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

44
views
michaelsipser
theoryofcomputation
regularlanguages
rotationalclosureoflanguage
descriptive
0
votes
0
answers
23
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

36
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
24
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

27
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
25
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

40
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
26
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

47
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
27
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

133
views
michaelsipser
theoryofcomputation
regularlanguages
pumpinglemma
proof
descriptive
0
votes
1
answer
28
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

96
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
29
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

29
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
30
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

48
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged regularlanguages
Recent Blog Comments
Q1. I don't know any trick or method, I usually...
Yeah, Now it's on.
Can you check now?
Even I filled NIELIT form which had similar...
Today's test will be late  either midnight or...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,572
answers
201,978
comments
95,388
users