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 closureproperty
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 2 Question 53 (Page No. 159)
Show that the class of DCFLs is not closed under the following operations: Union Intersection Concatenation Star Reversal
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.8k
points)

3
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 2 Question 50 (Page No. 159)
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 2 Question 49 (Page No. 159)
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.8k
points)

3
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
+1
vote
1
answer
4
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.6k
points)

87
views
cmi2019
regularlanguages
contextfreelanguage
closureproperty
0
votes
1
answer
5
Peter Linz Edition 4 Exercise 4.3 Question 24 (Page No. 124)
Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude from this that $L_2$ is regular?
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

32
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 4.3 Question 23 (Page No. 124)
Is the family of regular languages closed under infinite intersection?
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

21
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
7
Peter Linz Edition 4 Exercise 4.3 Question 22 (Page No. 124)
Consider the argument that the language associated with any generalized transition graph is regular. The language associated with such a graph is $L=\bigcup_{p∈P} L(r_p)$, where $P$ ... is regular. Show that in this case, because of the special nature of $P$, the infinite union is regular.
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

14
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 4.3 Question 21 (Page No. 124)
Let $P$ be an infinite but countable set, and associate with each $p ∈ P$ a language $L_p$. The smallest set containing every $L_p$ is the union over the infinite set $P$; it will be denoted by $U_{p∈p}L_p$. Show by example that the family of regular languages is not closed under infinite union.
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

19
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 4.3 Question 16 (Page No. 123)
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

18
views
peterlinz
theoryofcomputation
pumpinglemma
regularlanguages
closureproperty
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 4.3 Question 15 (Page No. 123)
Consider the languages below. For each, make a conjecture whether or not it is regular. Then prove your conjecture. (a) $L=$ {$a^nb^la^k:n+k+l \gt 5$} (b) $L=$ {$a^nb^la^k:n \gt 5,l> 3,k\leq l$} (c) $L=$ {$a^nb^l:n/l$ is an integer} (d) $L=$ ... $L=$ {$a^nb^l:n\geq 100,l\leq 100$} (g) $L=$ {$a^nb^l:nl=2$}
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

37
views
peterlinz
theoryofcomputation
regularlanguages
pumpinglemma
closureproperty
0
votes
1
answer
11
Peter Linz Edition 4 Exercise 4.3 Question 13 (Page No. 123)
Show that the following language is not regular. $L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k1$}.
asked
Apr 11
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

53
views
peterlinz
theoryofcomputation
pumpinglemma
regularlanguages
closureproperty
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 4.3 Question 10 (Page No. 123)
Consider the language $L=$ {$a^n:n$ is not a perfect square}. (a) Show that this language is not regular by applying the pumping lemma directly. (b) Then show the same thing by using the closure properties of regular languages.
asked
Apr 11
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

22
views
peterlinz
theoryofcomputation
pumpinglemma
regularlanguages
closureproperty
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 4.1 Question 26 (Page No. 110)
Let $G_1$ and $G_2$ be two regular grammars. Show how one can derive regular grammars for the languages (a) $L (G_1) ∪ L (G_2)$. (b) $L (G_1) L (G_2)$. (b) $L (G_1)^*$.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

5
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 4.1 Question 25 (Page No. 111)
The $min$ of a language $L$ is defined as $min(L)=$ {$w∈L:$ there is no $u∈L,v∈Σ^+,$ such that $w=uv$} Show that the family of regular languages is closed under the $ min$ operation.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

4
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 4.1 Question 24 (Page No. 111)
Define the operation $leftside$ on $L$ by $leftside(L)=$ {$w:ww^R∈L$} Is the family of regular languages closed under this operation?
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

11
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 4.1 Question 23 (Page No. 111)
Define an operation $minus5$ on a language $L$ as the set of all strings of $L$ with the fifth symbol from the left removed (strings of length less than five are left unchanged). Show that the family of regular languages is closed under the $minus5$ operation.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

10
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 4.1 Question 22 (Page No. 110)
The $shuffle$ of two languages $L_1$ and $L_2$ is defined as $shuffle(L_1,L_2)=$ {$w_1v_1w_2v_2w_3v_3...w_mv_m:w_1w_2w_3….w_m∈L_1, v_1v_2...v_m∈L_2$, for all $w_i,v_i∈Σ^*$}. Show that the family of regular languages is closed under the $shuffle$ operation.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

22
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 4.1 Question 21 (Page No. 110)
Define $exchange(a_1a_2a_3...a_{n1}a_n)=a_na_2a_3...a_{n1}a_1$, and $exchange(L)=$ {$v:v=exchange(w)$ for some $w∈L$} Show that the family of regular languages is closed under exchange.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

7
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 4.1 Question 20 (Page No. 110)
For a string $a_1a_2…a_n$ define the operation $shift$ as $shift(a_1a_2...a_n)=a_2a_3...a_na_1$ From this, we can define the operation on a language as $shift(L)=$ {$v:v=shift(w$ for some $w∈L$} Show that regularity is preserved under the shift operation.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

7
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 4.1 Question 19 (Page No. 110)
Define an operation $third$ on strings and languages as $third(a_1a_2a_3a_4a_5a_6...)=a_3a_6...$ with the appropriate extension of this definition to languages. Prove the closure of the family of regular languages under this operation.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

9
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 4.1 Question 18 (Page No. 110)
The $head$ of a language is the set of all prefixes of its strings, that is, $head(L)=$ {$x:xy∈L$ for some $y ∈Σ^*$} Show that the family of regular languages is closed under this operation.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

4
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 4.1 Question 17 (Page No. 110)
The $tail$ of a language is defined as the set of all suffixes of its strings, that is, $tail(L)=$ {$y:xy∈L$ for some $x∈Σ^*$} Show that if L is regular, so is $tail(L)$.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

3
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 4.1 Question 16 (Page No. 110)
Show that if the statement “If $L_1$ is regular and $L_1 ∪ L_2$ is also regular, then $L_2$ must be regular“ were true for all $L_1$ and $L_2$, then all languages would be regular.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

3
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 4.1 Question 15 (Page No. 110)
The left quotient of a language $L_1$ with respect to $L_2$ is defined as $L_2/L_1=$ {$y:x∈L_2,xy∈L_1$} Show that the family of regular languages is closed under the left quotient with a regular language.
asked
Apr 5
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

3
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
1
answer
25
Peter Linz Edition 4 Exercise 4.1 Question 14 (Page No. 109)
If $L$ is a regular language, prove that the language {$uv : u ∈ L,υ ∈ L^R$} is also regular.
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

15
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
1
answer
26
Peter Linz Edition 4 Exercise 4.1 Question 13 (Page No. 109)
If $L$ is a regular language, prove that $L_1 =$ {$uv : u ∈ L, υ = 2$} is also regular.
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

11
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 4.1 Question 12 (Page No. 109)
Suppose we know that $L_1 ∪ L_2$ is regular and that $L_1$ is finite. Can we conclude from this that $L_2$ is regular?
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

7
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 4.1 Question 11 (Page No. 109)
Show that $L_1 = L_1L_2/L_2$ is not true for all languages $L_1$ and $L_2$.
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

5
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 4.1 Question 10 (Page No. 109)
Let $L_1 = L (a^*baa^*)$ and $L_2 = L (aba^*)$. Find $L_1/L_2$.
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

6
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 4.1 Question 9 (Page No. 109)
Which of the following are true for all regular languages and all homomorphisms? (a) $h (L_1 ∪ L_2)= h (L_1) ∩ h (L_2)$. (b) $h (L_1 ∩ L_2)= h (L_1) ∩ h (L_2)$. (c) $h (L_1L_2) = h (L_1) h (L_2)$.
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15k
points)

10
views
peterlinz
theoryofcomputation
regularlanguages
closureproperty
Page:
1
2
3
4
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
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Resource to Learn Graph Theory Interactively
Follow @csegate
Recent questions tagged closureproperty
Recent Blog Comments
Are previous year question papers available,...
For JEST, applied for phd or integrated phd...
Thank you, Lakshman. Keep up the good work.
Is NOC need to send via registered post only? Or...
ok sir , I am resending it
50,666
questions
56,136
answers
193,695
comments
93,470
users