Register

Recent questions tagged regular-language

10.2k
views
2 answers
34 votes
GATE CSE 2011 | Question: 24
Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$. (For example, let $P$ be the language represented by the regular expression ... $P-Q$\Sigma^*-P$\Sigma^*-Q$
User Avatar
7.5k
views
3 answers
28 votes
GATE IT 2008 | Question: 35
Which of the following languages is (are) non-regular?$L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}$L_2 = \{w \mid w $ reads the same forward and backward$\ ... $L_2$ and $L_3$ only$L_1$ and $L_2$ only$L_3$ only$L_2$ only
User Avatar
1.9k
views
1 answers
1 votes
Regular or not ?
{ wxw | w belongs to {0,1}* , x belongs to {0,1}+ }
User Avatar
12.8k
views
2 answers
12 votes
proof regarding infinite union/intesection
Q1:Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices).Ans1: Consider the sets {0}, {01}, {0011}, etc. ... infinite union/ infinite intersection and also explain the answerThis question is from aduni.org
User Avatar
9.2k
views
2 answers
21 votes
GATE CSE 1996 | Question: 1.10
Let $L \subseteq \Sigma^*$ where $\Sigma = \left\{a,b \right\}$ ... regular$L = \left\{a^mb^n \mid m \geq 1, n \geq 1 \right \}$ is regular
User Avatar
16.2k
views
5 answers
26 votes
GATE CSE 1995 | Question: 2.24
Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n > 0\right\} $ then the languages $L \cup R$ and $R$ are respectivelyregular, regularnot regular, regularregular, not regularnot regular, not regular
User Avatar
26.0k
views
6 answers
118 votes
GATE CSE 2014 Set 2 | Question: 36
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'\text{s as }$ $(011)'\text{s} \}$ ... $L_2$ is regular but not $L_1$Both $L_1$ and $L_2$ are regularNeither $L_1$ nor $L_2$ are regular
User Avatar
11.0k
views
3 answers
44 votes
GATE CSE 2014 Set 2 | Question: 15
If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language$L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$Which one of the following is CORRECT?Only IOnly IIBoth I and IINeither I nor II
User Avatar
9.6k
views
3 answers
25 votes
GATE CSE 2014 Set 1 | Question: 15
Which one of the following is TRUE?The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ ... is regular.
User Avatar
6.6k
views
3 answers
23 votes
GATE CSE 1998 | Question: 2.6
Which of the following statements is false?Every finite subset of a non-regular set is regularEvery subset of a regular set is regularEvery finite subset of a regular set is regularThe intersection of two regular sets is regular
User Avatar
7.7k
views
4 answers
24 votes
GATE CSE 2012 | Question: 25
Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$?$ abaabaaabaa$ aaaabaaaa$ baaaaabaaaab$ baaaaabaa$\text{1, 2 and 3}$\text{2, 3 and 4}$\text{1, 2 and 4}$\text{1, 3 and 4}$
User Avatar
4.4k
views
4 answers
28 votes
GATE CSE 1999 | Question: 6
Given that $A$ is regular and $(A \cup B)$ is regular, does it follow that $B$ is necessarily regular? Justify your answer.Given two finite automata $M1, M2$, outline an algorithm to decide if $L(M1) \subset L(M2)$. (note: strict subset)
User Avatar
19.5k
views
5 answers
51 votes
GATE CSE 2013 | Question: 8
Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ?$\{\epsilon\}$\phi$a^*$\{\epsilon, a\}$
User Avatar
14.5k
views
2 answers
39 votes
GATE CSE 2007 | Question: 31
Which of the following languages is regular?$\left\{ww^R \mid w \in \{0, 1\}^+\right\}$\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$
User Avatar
15.7k
views
3 answers
38 votes
GATE CSE 2007 | Question: 7
Which of the following is TRUE?Every subset of a regular set is regularEvery finite subset of a non-regular set is regularThe union of two non-regular sets is not regularInfinite union of finite sets is regular
User Avatar
20.4k
views
8 answers
84 votes
GATE CSE 2006 | Question: 29
If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$'s in $s$ and $n_1(s)$ the number of $1$'s in $s$. Which one of the following languages is not ...
User Avatar
8.3k
views
5 answers
21 votes
GATE CSE 2001 | Question: 2.6
Consider the following languages:$L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ ... are regular?Only $L1$ and $L2$Only $L2, L3$ and $L4$Only $L3$ and $L4$Only $L3$
User Avatar
15.1k
views
2 answers
24 votes
GATE CSE 2001 | Question: 1.4
Consider the following two statements:$S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ ... $S_2$ is correctBoth $S_1$ and $S_2$ are correctNone of $S_1$ and $S_2$ is correct
User Avatar
4.9k
views
2 answers
28 votes
GATE CSE 2000 | Question: 7
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the substring $00$ nor the substring $11$. ... some condition. What is the condition on the values of $i$ and $j$?
User Avatar
9.3k
views
6 answers
39 votes
GATE CSE 2000 | Question: 2.8
What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states?$L$ must be $\{a^n \mid n \ \text{ is odd}\}$ ... $L$ must be $\{a^n \mid n \text{ is even}\}$
User Avatar
8.5k
views
1 answers
21 votes
GATE CSE 1991 | Question: 03,xiv
Which of the following is the strongest correct statement about a finite language over some finite alphabet $\Sigma?$It could be undecidableIt is Turing-machine ... a context-sensitive language.It is a regular language.None of the above,
User Avatar
9.9k
views
2 answers
34 votes
GATE CSE 2008 | Question: 53
Which of the following are regular sets?$\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ ... I and IV onlyI and III onlyI onlyIV only
User Avatar
1.4k
views
2 answers
5 votes
Which of the following are useful in proving a language to be regular?
Which of the following are useful in proving a language to be regular?Myhill-Nerode theoremPumping lemmaDrawing an NFAForming a regular expression(A) All of these(B) 1, 3 and 4 only(C) 2, 3 and 4 only(D) 3 and 4 only
User Avatar
846
views
1 answers
3 votes
Let L be a regular language
Let $L$ be a regular language and $w$ be a string in $L$. If $w$ can be split into $x, y$ and $z$ such that $|xy| \leq$ number of states in the minimal DFA for $L$, ... $\forall i \in N, xy^iz \in L$(D) $\exists i \in N, xy^iz \notin L$
User Avatar
Page: