Dark Mode

Recent questions tagged closure-property

2 votes

0 answers

1

#Self Doubt
Suppose L1 = CFL and L2 = Regular, We are to find out whether L1 - L2 = CFL or non CFL. I have 2 approaches to this question and I am confused which is wrong: L1 - L2 = L1 intersection L2' L2 being Regular L2' is also Regular so CFL ... being Regular L2' is also Regular and every Regular Language is also CFL so CFL intersection CFL = non CFL. Can somebody please clarify my doubt?

Sunnidhya Roy asked in Theory of Computation Dec 11, 2022

by Sunnidhya Roy

91 views

0 votes

0 answers

2

Made easy Theory of Computation
Which of them are not regular- (a) L={a^m b^n | n>=2023, m<=2023} (b) L={a^n b^m c^l | n=2023, m>2023, l>m} according made easy (b) is the answer but can we do like this- Let L1= {a^n |n=2023} ... ) and so L2 is regular L=L1.L2 (regular lang are closed under concatenation) therefore L is regular.this makes option (b) regular is it right approach ?

Shreya2002 asked in Theory of Computation Dec 2, 2022

114 views

0 votes

2 answers

3

ACE 2023 Test series: TOC: Basic properties

abhinowKatore asked in Theory of Computation Oct 18, 2022

by abhinowKatore

237 views

1 vote

1 answer

4

Igate Test Series
please explain all options with example

Amit Mehta asked in Theory of Computation Jul 20, 2022

255 views

0 votes

1 answer

5

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

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

226 views

0 votes

0 answers

6

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$.

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

145 views

0 votes

1 answer

7

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

728 views

2 votes

3 answers

8

CMI2019-A-1
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 context-free context-free, but not regular both regular and context-free neither regular nor context-free

gatecse asked in Theory of Computation Sep 13, 2019

618 views

0 votes

2 answers

9

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?

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

260 views

0 votes

2 answers

10

Peter Linz Edition 4 Exercise 4.3 Question 23 (Page No. 124)
Is the family of regular languages closed under infinite intersection?

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

221 views

0 votes

0 answers

11

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.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

131 views

0 votes

0 answers

12

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.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

135 views

1 vote

1 answer

13

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

204 views

0 votes

0 answers

14

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:|n-l|=2$}

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

223 views

0 votes

1 answer

15

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 k-1$}.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

227 views

2 votes

0 answers

16

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

188 views

0 votes

0 answers

17

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)^*$.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

125 views

0 votes

0 answers

18

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.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

118 views

0 votes

0 answers

19

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?

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

143 views

0 votes

0 answers

20

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.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

187 views

0 votes

0 answers

21

Peter Linz Edition 4 Exercise 4.1 Question 22 (Page No. 110)
The $\textit{shuffle}$ of two languages $L_1$ and $L_2$ is defined as $\textit{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,\text{ for all }w_i,v_i∈Σ^*\}.$ Show that the family of regular languages is closed under the $shuffle$ operation.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

170 views

1 vote

0 answers

22

Peter Linz Edition 4 Exercise 4.1 Question 21 (Page No. 110)
Define $exchange(a_1a_2a_3...a_{n-1}a_n)=a_na_2a_3...a_{n-1}a_1$, and $exchange(L)=$ {$v:v=exchange(w)$ for some $w∈L$} Show that the family of regular languages is closed under exchange.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

239 views

0 votes

0 answers

23

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.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

158 views

0 votes

0 answers

24

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.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

135 views

0 votes

0 answers

25

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.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

142 views

0 votes

0 answers

26

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)$.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

101 views

0 votes

0 answers

27

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.

Naveen Kumar 3 asked in Theory of Computation Apr 5, 2019

by Naveen Kumar 3

99 views

Page:

1
2
3
4
next »

Recent questions tagged closure-property