Recent questions tagged regular-languages
Register

Recent questions tagged regular-languages

Recent questions tagged regular-languages
1 vote
0 answers 37 views
complement of language
How to find complement of language.? complement of recursive language is recursive. while complement of context free language is context sensitive language.
TheShivam asked in Theory of Computation Aug 16
by TheShivam
9 points
37 views
0 votes
0 answers 33 views
Regular Grammar
Is S--> AccB A-->aA/a B-->bB/a a regular grammar according to the type 3 grammar rule i.e, production must be in the form S-->Ax or S-->xA where A is non terminal and x is terminal?
Shubhranshu asked in Theory of Computation Aug 1
by Shubhranshu
5 points
33 views
0 votes
0 answers 40 views
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
promise asked in Theory of Computation Jun 8
by promise
5 points
40 views
0 votes
0 answers 243 views
Regular Expression/Language
Set of possible strings generated by Regular expression (11+111)* should contain {null, {11}, {111}, {11111},…}. Can this set contain the strings which are generated considering the part of the above RE partially, i.e., will {1111} (length 4), generated by considering either {11} partially or {111} partially. Can such string be a part of the language ?
hridayN asked in Theory of Computation Apr 25, 2020
by hridayN
5 points
243 views
0 votes
0 answers 20 views
GATE2014-2-36 Video Solution
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ ... following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
20 views
0 votes
0 answers 14 views
GATE2018-52 Video Solution
Given a language $L$, define $L^i$ as follows:$L^0 = \{ \varepsilon \}$$L^i = L^{i-1} \bullet L \text{ for all } I >0$The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
14 views
0 votes
0 answers 14 views
GATE2006-29 Video Solution
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 regular? $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$ ... $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
14 views
0 votes
0 answers 13 views
GATE2013-8 Video Solution
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\}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
13 views
0 votes
0 answers 10 views
GATE2006-IT-81 Video Solution
Let $L$ be a regular language. Consider the constructions on $L$ below: $\text{repeat} (L) = \{ww \mid w \in L\}$ $\text{prefix} (L) = \{u \mid \exists v : uv \in L\}$ $\text{suffix} (L) = \{v \mid \exists u: uv \in L\}$ ... is best suited to support your answer above? $(a + b)^*$ $\{\epsilon, a, ab, bab\}$ $(ab)^*$ $\{a^nb^n \mid n \geq 0\}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
10 views
0 votes
0 answers 8 views
GATE2007-31 Video Solution
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\}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
8 views
0 votes
0 answers 17 views
GATE2007-7 Video Solution
Which of the following is TRUE? Every subset of a regular set is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Infinite union of finite sets is regular
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
17 views
0 votes
0 answers 18 views
GATE2016-2-18 Video Solution
Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Context-free, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRUE ? $\overline{L_{3}} \cup L_{4}$ is recursively enumerable. $\overline{L_{2}} \cup L_{3}$ ... $L_{1} \cup \overline{L_{2}}$ is context-free. I only. I and III only. I and IV only. I, II and III only.
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
18 views
0 votes
0 answers 12 views
GATE2015-2-51 Video Solution
Which of the following is/are regular languages? $L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w$ $L_2: \left\{ a^nb^m \mid m \neq n \text { and } m, n \geq 0 \right\}$ $L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}$ $L_1$ and $L_3$ only $L_2$ only $L_2$ and $L_3$ only $L_3$ only
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
12 views
0 votes
0 answers 16 views
GATE2019-7 Video Solution
If $L$ is a regular language over $\Sigma = \{a,b\} $, which one of the following languages is NOT regular? $L.L^R = \{xy \mid x \in L , y^R \in L\}$ $\{ww^R \mid w \in L \}$ $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$ $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
16 views
0 votes
0 answers 13 views
GATE2011-24 Video Solution
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^*$ and $Q$ be $\{p^nq^n \mid n \in N\})$. Then which of the following is ALWAYS regular? $P \cap Q$ $P-Q$ $\Sigma^*-P$ $\Sigma^*-Q$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
13 views
0 votes
0 answers 13 views
GATE2006-IT-80 Video Solution
Let $L$ be a regular language. Consider the constructions on $L$ below: repeat $(L) = \{ww \mid w \in L\}$ prefix $(L) = \{u \mid ∃v : uv \in L\}$ suffix $(L) = \{v \mid ∃u : uv \in L\}$ half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$ Which of the constructions could lead to a non-regular language? Both I and IV Only I Only IV Both II and III
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
13 views
0 votes
0 answers 14 views
GATE2014-2-15 Video Solution
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 I Only II Both I and II Neither I nor II
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
14 views
0 votes
0 answers 11 views
GATE2008-53 Video Solution
Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$ I and IV only I and III only I only IV only
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
11 views
0 votes
0 answers 8 views
GATE2014-1-15 Video Solution
Which one of the following is TRUE? The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular. The language $L$ ... $L = \left\{ww \mid w \in \Sigma^* \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
8 views
0 votes
0 answers 12 views
GATE2000-2.8 Video Solution
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}\}$ $L$ must be $\{a^n \mid n \geq 0\}$ Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
12 views
0 votes
0 answers 13 views
GATE2016-2-17 Video Solution
Language $L_{1}$ is defined by the grammar: $S_{1} \rightarrow a S_{1} b \mid \varepsilon$ Language $L_{2}$ is defined by the grammar: $S_{2} \rightarrow a b S_{2} \mid \varepsilon$ Consider the following statements: P: $L_{1}$ is regular Q: $L_{2}$ is regular ... $Q$ are true. $P$ is true and $Q$ is false. $P$ is false and $Q$ is true. Both $P$ and $Q$ are false.
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
13 views
0 votes
0 answers 12 views
GATE2001-2.6 Video Solution
Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ ... $L1$ and $L2$ Only $L2, L3$ and $L4$ Only $L3$ and $L4$ Only $L3$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
12 views
0 votes
0 answers 10 views
GATE2001-1.4 Video Solution
Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct? Only $S_1$ is correct Only $S_2$ is correct Both $S_1$ and $S_2$ are correct None of $S_1$ and $S_2$ is correct
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
10 views
0 votes
0 answers 12 views
GATE2006-IT-30 Video Solution
Which of the following statements about regular languages is NOT true ? Every language has a regular superset Every language has a regular subset Every subset of a regular language is regular Every subset of a finite language is regular
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
12 views
0 votes
0 answers 10 views
GATE1990-3-viii Video Solution
Choose the correct alternatives (More than one may be correct). Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then: $R_{1} \cap R_{2}$ is not regular. $R_{1} \cup R_{2}$ is regular. $\Sigma^{*}-R_{1}$ is regular. $R_{1}^{*}$ is not regular.
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
10 views
0 votes
0 answers 10 views
GATE1998-2.6 Video Solution
Which of the following statements is false? Every finite subset of a non-regular set is regular Every subset of a regular set is regular Every finite subset of a regular set is regular The intersection of two regular sets is regular
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
10 views
0 votes
0 answers 12 views
GATE1995-2.24 Video Solution
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 respectively regular, regular not regular, regular regular, not regular not regular, not regular
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
12 views
0 votes
0 answers 8 views
GATE2012-25 Video Solution
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}$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
8 views
0 votes
0 answers 35 views
GATE1991-03,xiv Video Solution
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which of the following is the strongest correct statement about a finite language over some finite alphabet $\Sigma$ ? It could be undecidable It is Turing-machine recognizable It is a context sensitive language. It is a regular language. None of the above,
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
35 views
0 votes
0 answers 16 views
GATE2008-IT-35 Video Solution
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_3 = \{w \in \{0, 1\} ^* \mid w$ contains an even number of 0's and an even number of 1's$\}$ $L_2$ and $L_3$ only $L_1$ and $L_2$ only $L_3$ only $L_2$ only
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
16 views
0 votes
0 answers 16 views
GATE2000-7 Video Solution
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the sub string $00$ nor the sub string $11$. Consider the grammar S → aSAb S → ∊ A → bA A → ∊ where $S$, $A$ are non-terminal symbols with ... $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
16 views
0 votes
0 answers 19 views
GATE1999-6 Video Solution
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)
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
19 views
0 votes
0 answers 9 views
GATE1996-1.10 Video Solution
Let $L \subseteq \Sigma^*$ where $\Sigma = \left\{a,b \right\}$. Which of the following is true? $L = \left\{x \mid x \text{ has an equal number of } a\text{'s and }b\text{'s}\right \}$ is regular $L = \left\{a^nb^n \mid n \geq 1\right \}$ ... $L = \left\{a^mb^n \mid m \geq 1, n \geq 1 \right \}$ is regular
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
9 views
0 votes
0 answers 14 views
GATE1990-15a Video Solution
Is the language generated by the grammar $G$ regular? If so, give a regular expression for it, else prove otherwise G: $S \rightarrow aB$ $B \rightarrow bC$ $C \rightarrow xB$ $C \rightarrow c$
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
14 views
0 votes
0 answers 20 views
GATE1987-2h Video Solution
State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.
admin asked in Theory of Computation Apr 18, 2020
by admin
581 points
20 views
Page:
Ask
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Developed by Chun