Regular Language

Question 1
Consider the following two statements about regular languages:

S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.

Which one of the following choices is correct?
A
Only S1 is true
B
Only S2 is true
C
Both S1 and S2 are true
D
Neither S1 nor S2 is true
GATE CSE 2021 SET-2   Theory of Computation
Question 2
Let L \subseteq \{0,1\}^* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?
A
L - \{01\}
B
L \cup \{01\}
C
\{0,1\}^* -L
D
L \cdot L
GATE CSE 2021 SET-2   Theory of Computation
Question 3
Which of the following is true?
A
Every subset of a regular set is regular
B
Every finite subset of non-regular set is regular
C
The union of two non regular set is not regular
D
Infinite union of finite set is regular
ISRO CSE 2020   Theory of Computation
Question 4
Consider the following statements.

I. If L_1\cup L_2 is regular, then both L_1 \; and \; L_2 must be regular.
II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?
A
I only
B
II only
C
Both I and II
D
Neither I nor II
GATE CSE 2020   Theory of Computation
Question 5
For \Sigma =\{a,b\}, let us consider the regular language
L=\{x|x=a^{2+3k} \; or \; x=b^{10+12k}, k\geq 0\}.
Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A
3
B
5
C
9
D
24
GATE CSE 2019   Theory of Computation
Question 6
If L is a regular language over \Sigma =\{a,b\}, which one of the following languages is NOT regular ?
A
L\cdot L^R=\{xy|x \in L,y^R \in L\}
B
\{ww^R|w \in L\}
C
Prifix(L)={x \in \Sigma ^*|\exists y \in \Sigma ^* such that xy \in L}
D
Suffix(L)={y \in \Sigma ^*|\exists x \in \Sigma ^* such that xy \in L}
GATE CSE 2019   Theory of Computation
Question 7
Choose the correct statement -
A
A=\left\{a^{n} b^{n} \mid n=1,2,3, \ldots\right\} is a regular language
B
The set B, consisting of all strings made up of only a^{\prime} s and b^{\prime} s having equal number of a^{\prime} s and bs defines a regular language
C
L\left(A^{*} B\right) \cap B gives the set A
D
None of the above
ISRO CSE 2018   Theory of Computation
Question 8
Language L1 is defined by the grammar: S_{1}\rightarrow aS_{1}b|\varepsilon
Language L2 is defined by the grammar: S_{2}\rightarrow abS_{2}|\varepsilon
Consider the following statements:
P: L1 is regular
Q: L2 is regular
Which one of the following is TRUE?
A
Both P and Q are true
B
P is true and Q is false
C
P is false and Q is true
D
Both P and Q are false
GATE CSE 2016 SET-2   Theory of Computation
Question 9
Let R_{1} and R_{2} be regular sets defined over the alphabet, then
A
R_{1} \cap R_{2} is not regular
B
R_{1} \cup R_{2} is not regular
C
\Sigma^{*}-R_{1} is regular
D
R_{1}^{*} is not regular
ISRO CSE 2015   Theory of Computation
Question 10
Which of the following languages is/are regular?
L_{1}:\{wxw^{R}|w,x \in \{a,b\}^{*} \; and \; |w|,|x| \gt 0 \}, w^{R} is the reverse of string w
L_{2}:\{a^{n}b^{m}|m\neq n \; and \; m,n\geq 0\}
L_{3}:\{a^{p}b^{q}c^{r}|p,q,r\geq 0\}
A
L1 and L3 only
B
L2 only
C
L2 and L3 only
D
L3 only
GATE CSE 2015 SET-2   Theory of Computation
There are 10 questions to complete.

5 thoughts on “Regular Language”

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.