Recent questions tagged regular-languages - GATE Overflow

0 votes

1 answer

1

UGCNET-Jan2017-III: 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

0 votes

2 answers

2

UGCNET-Jan2017-III: 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

0 votes

2 answers

3

UGCNET-Jan2017-III: 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

+2 votes

2 answers

4

ISRO2020-38
Which of the following is true? Every subset of a regular set is regular Every finite subset of non-regular 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

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

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

+1 vote

1 answer

7

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 14, 2019 in Theory of Computation by gatecse | 171 views

0 votes

1 answer

8

CMI2019-B-1
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

+2 votes

3 answers

9

CMI2018-A-1
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

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

+3 votes

2 answers

11

MadeEasy Test Series: Theory Of Computation - Regular Languages
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \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

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

+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

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

0 votes

1 answer

15

Michael Sipser Edition 3 Exercise 2 Question 18 (Page No. 156)
Let $C$ be a context-free language and $R$ be a regular language$.$ Prove that the language $C\cap R$ is context-free. 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

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 context-free grammar$.$

asked May 4, 2019 in Theory of Computation by Lakshman Patel RJIT | 22 views

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

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

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

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

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

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

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

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{xz|for 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

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{x|for 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

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

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

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

0 votes

0 answers

29

Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,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

0 votes

1 answer

30

Michael Sipser Edition 3 Exercise 1 Question 49 (Page No. 90)
Let $B=\{1^{k}y|y\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}y|y\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

Page:

1
2
3
4
5
6
...
20
next »

Recent questions tagged regular-languages

52,375 questions

60,572 answers

201,978 comments

95,388 users