search
Log In

Recent questions tagged regular-languages

0 votes
2 answers
1
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
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
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
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
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
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
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
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
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
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
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
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
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
3 votes
1 answer
17
0 votes
1 answer
19
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
0 votes
1 answer
21
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
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
0 votes
1 answer
24
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
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
0 votes
0 answers
27
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
...