Recent questions tagged regular-languages
Register

Recent questions tagged regular-languages

Recent questions tagged regular-languages
1 vote
0 answers 53 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, 2021
by TheShivam
9 points
53 views
0 votes
0 answers 45 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, 2021
by Shubhranshu
5 points
45 views
0 votes
0 answers 60 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, 2021
by promise
5 points
60 views
0 votes
0 answers 332 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
332 views
0 votes
0 answers 24 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
585 points
24 views
0 votes
0 answers 20 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
585 points
20 views
0 votes
0 answers 18 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
585 points
18 views
0 votes
0 answers 16 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
585 points
16 views
0 votes
0 answers 13 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
585 points
13 views
0 votes
0 answers 10 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
585 points
10 views
0 votes
0 answers 19 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
585 points
19 views
0 votes
0 answers 23 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
585 points
23 views
0 votes
0 answers 16 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
585 points
16 views
0 votes
0 answers 22 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
585 points
22 views
0 votes
0 answers 18 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
585 points
18 views
0 votes
0 answers 17 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
585 points
17 views
0 votes
0 answers 17 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
585 points
17 views
0 votes
0 answers 14 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
585 points
14 views
0 votes
0 answers 11 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
585 points
11 views
0 votes
0 answers 14 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
585 points
14 views
0 votes
0 answers 15 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
585 points
15 views
0 votes
0 answers 16 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
585 points
16 views
0 votes
0 answers 14 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
585 points
14 views
0 votes
0 answers 14 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
585 points
14 views
0 votes
0 answers 16 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
585 points
16 views
0 votes
0 answers 13 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
585 points
13 views
0 votes
0 answers 16 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
585 points
16 views
0 votes
0 answers 10 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
585 points
10 views
0 votes
0 answers 41 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
585 points
41 views
0 votes
0 answers 19 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
585 points
19 views
0 votes
0 answers 19 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
585 points
19 views
0 votes
0 answers 21 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
585 points
21 views
0 votes
0 answers 12 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
585 points
12 views
0 votes
0 answers 18 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
585 points
18 views
0 votes
0 answers 24 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
585 points
24 views
Page:
Ask a Question
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