menu
search
Log In
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

Subjects

Recent questions tagged regular-languages

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged regular-languages

0 votes
2 answers
1
UGCNET-Oct2020-II: 56
Consider the following languages: $L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$ $L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$ $L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$ Which of the languages is(are) regular? Choose the correct answer from the options given below: $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_1$ only $L_2$ only
Consider the following languages: $L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$ $L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$ $L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$ Which of the languages is(are) regular? Choose the correct answer from the options given below: $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_1$ only $L_2$ only
asked Nov 20, 2020 in Theory of Computation jothee 83 views
2 votes
5 answers
3
NIELIT 2016 MAR Scientist B - Section C: 27
If $L$ be a language recognizable by a finite automaton, then language from $\{L\} = \{w$ such that $w$ is a prefix of $v$ where $v\in L\}$, is a regular language. context-free language. context-sensitive language. recursive enumeration language
If $L$ be a language recognizable by a finite automaton, then language from $\{L\} = \{w$ such that $w$ is a prefix of $v$ where $v\in L\}$, is a regular language. context-free language. context-sensitive language. recursive enumeration language
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 300 views
0 votes
4 answers
4
NIELIT 2016 MAR Scientist B - Section C: 28
Which of the following statements is correct? $A=\{a^nb^n\mid n= 0,1,2,3\dots \}$ is regular language Set $B$ of all strings of equal number of $a$'s and $b$'s defines a regular language $L(A^*B^*) \cap B$ gives the set $A$ None of these.
Which of the following statements is correct? $A=\{a^nb^n\mid n= 0,1,2,3\dots \}$ is regular language Set $B$ of all strings of equal number of $a$'s and $b$'s defines a regular language $L(A^*B^*) \cap B$ gives the set $A$ None of these.
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 240 views
0 votes
2 answers
5
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
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, 2020 in Theory of Computation jothee 219 views
1 vote
3 answers
6
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}$
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, 2020 in Theory of Computation jothee 199 views
1 vote
3 answers
7
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
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 (b) are false Both (a) and (b) are true (a) is true, (b) is false (a) is false, (b) is true
asked Mar 24, 2020 in Theory of Computation jothee 200 views
2 votes
3 answers
8
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
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 13, 2020 in Theory of Computation Satbir 413 views
0 votes
0 answers
10
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.
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 12, 2019 in Theory of Computation Lakshman Patel RJIT 36 views
1 vote
1 answer
11
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
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 gatecse 273 views
0 votes
2 answers
12
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.$
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 13, 2019 in Theory of Computation gatecse 324 views
2 votes
3 answers
13
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$
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 13, 2019 in Theory of Computation gatecse 438 views
0 votes
0 answers
14
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.
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 solution. Thus, prove that it is ... closed under inverse homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 95 views
4 votes
3 answers
15
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
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 Hirak 772 views
0 votes
1 answer
16
self doubt: TOC
is union of regular language and context free language always regular?
is union of regular language and context free language always regular?
asked May 22, 2019 in Theory of Computation Hirak 125 views
3 votes
1 answer
17
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
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 logan1x 344 views
0 votes
1 answer
19
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$.$
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 Lakshman Patel RJIT 64 views
0 votes
0 answers
20
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$.$
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 Lakshman Patel RJIT 44 views
0 votes
1 answer
21
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$.$
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 Lakshman Patel RJIT 103 views
0 votes
0 answers
22
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.$
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 Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 120 views
2 votes
1 answer
23
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.
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 Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 131 views
0 votes
1 answer
24
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.
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 Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 166 views
0 votes
0 answers
25
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}.$
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 and the middle part in placed first in the ... which $\text{CUT(B)$\neq$ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 134 views
0 votes
0 answers
26
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.
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 Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 111 views
0 votes
0 answers
27
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.$
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 strings that are not in $B.$ Show that if $B$ and $D$ are two regular languages where $B\subseteqq D,$ then we can find a regular language $C$ where $B\subseteqq C\subseteqq D.$
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 83 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...