Recent questions tagged closure-property - GATE Overflow

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, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (59.4k points) | 7 views

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, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (59.4k points) | 6 views

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, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (59.4k points) | 8 views

+1 vote

1 answer

4

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

asked Sep 13, 2019 in Theory of Computation by gatecse Boss (17.5k points) | 108 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 36 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 22 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 14 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 20 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 19 views

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

asked Apr 12, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 37 views

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

asked Apr 11, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 56 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 23 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 5 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 4 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 11 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 10 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 22 views

0 votes

0 answers

18

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.

asked Apr 5, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 8 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 7 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 9 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 4 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 3 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 3 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 3 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 19 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 15 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 10 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 8 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 8 views

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, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 13 views

Page:

1
2
3
4
next »

Recent questions tagged closure-property

50,737 questions

57,389 answers

198,585 comments

105,434 users