Regular Expressions and Languages Questions and Answers

Q: For which of the following applications regular expressions can be used ?

Regular expressions can be used for all of the above.They describe the tokens recognised by the lexical analyser when designing compilers, power the search-and-replace features of text editors, and, because they are equivalent to finite automata, model the behaviour of sequential circuits, which are finite-state machines.Since each listed application is a genuine use, no single option is complete.

Q: Which of the following is NOT recognized by a finite automaton ?

The language not recognised by a finite automaton is \(a^{n} b^{n}\) where n ≥ 0.To accept anbn a machine must count the a's to check that the same number of b's follows, and n is unbounded. A finite automaton has only finitely many states, so it cannot keep an unbounded count, and the pumping lemma proves the language is not regular. A pushdown automaton can accept it with its stack, because the language is context-free.a*b*, (a+b)* and ab*a are regular expressions, so each describes a regular language that some finite automaton accepts.

Q: Let w be a string defined on the alphabet {0, 1} then which of the following language is regular ?

The regular language is L = {w | w has even number of 0's and even number of 1's}.A DFA needs to remember only two bits of information: whether it has seen an even or odd number of 0s, and of 1s. Four states (even-even, even-odd, odd-even, odd-odd) suffice, with even-even as the start and accepting state, so the language is regular.The other three need unbounded counting or memory. Equal numbers of 0s and 1s and more 0s than 1s need a counter, and w followed by its reverse needs a stack; each can be shown non-regular with the pumping lemma and is context-free.

Q: Kleene closure

Kleene closure is zero or more occurrences of the symbol.For a symbol a, the Kleene closure a* is the set of all strings of zero or more a's:\[ a^{*} = \{ \varepsilon, a, aa, aaa, \ldots \} \]It includes the empty string ε. 'One or more occurrences' describes the positive closure a+, which leaves ε out. 'Cleanly closes the token' is a pun on the name with no meaning.

11.

For which of the following applications regular expressions can be used ?

A.Designing compilers
B.Developing text editors
C.Simulating sequential circuits
D.All of the above

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: D

Regular expressions can be used for all of the above.

They describe the tokens recognised by the lexical analyser when designing compilers, power the search-and-replace features of text editors, and, because they are equivalent to finite automata, model the behaviour of sequential circuits, which are finite-state machines.

Since each listed application is a genuine use, no single option is complete.

Discuss in Forum

12.

Which of the following is NOT recognized by a finite automaton ?

A.a*b*
B.(a+b)*
C.\(a^{n} b^{n}\) where n ≥ 0
D.ab*a

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The language not recognised by a finite automaton is \(a^{n} b^{n}\) where n ≥ 0.

To accept aⁿbⁿ a machine must count the a's to check that the same number of b's follows, and n is unbounded. A finite automaton has only finitely many states, so it cannot keep an unbounded count, and the pumping lemma proves the language is not regular. A pushdown automaton can accept it with its stack, because the language is context-free.

a*b*, (a+b)* and ab*a are regular expressions, so each describes a regular language that some finite automaton accepts.

Discuss in Forum

13.

Let w be a string defined on the alphabet {0, 1} then which of the following language is regular ?

A.L = {\(ww^{R}\) | \(w^{R}\) is the reverse of w}
B.L = {w | w has equal number of 0's and 1's}
C.L = {w | w has even number of 0's and even number of 1's}
D.L = {w | w has more 0's than 1's}

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The regular language is L = {w | w has even number of 0's and even number of 1's}.

A DFA needs to remember only two bits of information: whether it has seen an even or odd number of 0s, and of 1s. Four states (even-even, even-odd, odd-even, odd-odd) suffice, with even-even as the start and accepting state, so the language is regular.

The other three need unbounded counting or memory. Equal numbers of 0s and 1s and more 0s than 1s need a counter, and w followed by its reverse needs a stack; each can be shown non-regular with the pumping lemma and is context-free.

Discuss in Forum

14.

Kleene closure

A.cleanly closes the token
B.is one or more occurrences of the symbol
C.is zero or more occurrences of the symbol
D.None of these

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: C

Kleene closure is zero or more occurrences of the symbol.

For a symbol a, the Kleene closure a* is the set of all strings of zero or more a's:

\[ a^{*} = \{ \varepsilon, a, aa, aaa, \ldots \} \]

It includes the empty string ε. 'One or more occurrences' describes the positive closure a⁺, which leaves ε out. 'Cleanly closes the token' is a pun on the name with no meaning.

Discuss in Forum

15.

Which of the following regular expression identities are true ?

A.(r + s)* = r* s*
B.(r + s)* = r* + s*
C.(r + s)* = (r*s*)*
D.r* s* = r* + s*

Exam Year(s)

UGC NET - 2012,

Answer: C

The identity \((r+s)^* = (r^* s^*)^*\) is true, since both sides describe all strings made of any number of r's and s's in any order. The identity \((r+s)^* = r^* s^*\) is false because the right side cannot produce a string such as sr in which s comes before r, and \((r+s)^* = r^* + s^*\) is false for the same reason, as \(r^* + s^*\) has no string mixing the two. The last identity, \(r^* s^* = r^* + s^*\), is false, because the left side gives rs but the right side does not. The keyed answer is the third option.

Discuss in Forum

16.

Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains

A.n states
B.n + 1 states
C.n + 2 states
D.\(2^{n}\) states

Exam Year(s)

UGC NET - 2012,

Answer: B

The language of the expression (a + b) repeated n times is the set of all strings of length exactly n over a and b. An automaton that counts the symbols needs one state for each count from 0 to n, which is n + 1 states, with the last one accepting; a complete deterministic automaton would also need a dead state for longer strings, but the key counts the n + 1 states of the counting chain. So the answer is n + 1 states, option (B). Fewer than n + 1 states cannot count to n, and the other options count more than are needed.

Discuss in Forum

17.

The regular expression for the following DFA is

A DFA with two states. The start state, marked by an arrow, loops on a and goes to the final (double-circled) state on b. The final state loops on b and returns to the start state on a.

A.ab*(b + aa*b)*
B.a*b(b + aa*b)*
C.a*b(b* + aa*b)
D.a*b(b * + aa*b)*

Exam Year(s)

UGC NET - 2012,

Answer: D

The DFA has a start state that loops on a and goes to the final state on b, and the final state loops on b and returns to the start state on a. From the start, any number of a's then a b brings us to the final state, which gives a*b. From the final state each round trip is either a b loop, or an a back to the start followed by any number of a's and a b, which is aa*b, so the expression is a*b(b + aa*b)*, option (B). Option (A) starts with one a, so it cannot generate the string b, which the DFA accepts, and options (C) and (D) put a star on the wrong part of the second factor.

Discuss in Forum

18.

Regular expression for the language \(L = \{ w \in \{0, 1\}^{*} \mid w\) has no pair of consecutive zeros\(\}\) is

A.\((1 + 010)^{*}\)
B.\((01 + 10)^{*}\)
C.\((1 + 010)^{*}(0 + \lambda)\)
D.\((1 + 01)^{*}(0 + \lambda)\)

Exam Year(s)

UGC NET - 2013,

Answer: D

Strings with no pair of consecutive zeros are those in which every 0 is followed by a 1, apart from a final 0. The expression \((1 + 01)^{*}(0 + \lambda)\) builds the string from the blocks 1 and 01 and allows one last 0 or nothing.

The expression \((1 + 010)^{*}\) cannot generate the string 01, \((01 + 10)^{*}\) cannot generate 1, and \((1 + 010)^{*}(0 + \lambda)\) cannot generate 01 either. Option D is correct.

Discuss in Forum

19.

A regular grammar for the language \(L = \{a^{n}b^{m} \mid n \text{ is even and } m \text{ is even}\}\) is given by

A.\(S \rightarrow aSb \mid S_{1};\ S_{1} \rightarrow bS_{1}a \mid \lambda\)
B.\(S \rightarrow aaS \mid S_{1};\ S_{1} \rightarrow bSb \mid \lambda\)
C.\(S \rightarrow aSb \mid S_{1};\ S_{1} \rightarrow S_{1}ab \mid \lambda\)
D.\(S \rightarrow aaS \mid S_{1};\ S_{1} \rightarrow bbS_{1} \mid \lambda\)

Exam Year(s)

UGC NET - 2013,

Answer: D

The grammar \(S \rightarrow aaS \mid S_{1};\ S_{1} \rightarrow bbS_{1} \mid \lambda\) generates exactly the strings with an even number of a's followed by an even number of b's. S produces pairs of a's and then passes to \(S_{1}\), which produces pairs of b's and stops, so n and m are both even.

The first and third options use rules such as \(S \rightarrow aSb\) that match an a with a b, which gives strings of the form \(a^{n}b^{n}\), and they are not regular grammars. The second has the rule \(S_{1} \rightarrow bSb\), which returns to S, and also is not a regular grammar of the required language.

Discuss in Forum

20.

The regular grammar for the language \(L = \{w \mid n_{a}(w)\) and \(n_{b}(w)\) are both even, \(w \in \{a, b\}^{*}\}\) is given by : (Assume, p, q, r and s are states)

A.\[\begin{aligned} p &\to aq \mid br \mid \lambda,\ q \to bs \mid ap \\ r &\to as \mid bp,\ s \to ar \mid bq \end{aligned}\] p and s are initial and final states.
B.\[\begin{aligned} p &\to aq \mid br,\ q \to bs \mid ap \\ r &\to as \mid bp,\ s \to ar \mid bq \end{aligned}\] p and s are initial and final states.
C.\[\begin{aligned} p &\to aq \mid br \mid \lambda,\ q \to bs \mid ap \\ r &\to as \mid bp,\ s \to ar \mid bq \end{aligned}\] p is both initial and final states.
D.\[\begin{aligned} p &\to aq \mid br,\ q \to bs \mid ap \\ r &\to as \mid bp,\ s \to ar \mid bq \end{aligned}\] p is both initial and final states.

Exam Year(s)

UGC NET - 2014,

Answer: C

The grammar in which p has a lambda production and p is both the initial and the final state is correct. The language has an even number of a's and an even number of b's, so the empty string belongs to it, and the machine must accept in the state that stands for even-even, which is also where it starts. States q, r and s stand for odd-even, even-odd and odd-odd, and each transition adds one symbol. The options with two final states, or without the lambda production, either accept strings of the wrong parity or reject the empty string.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Regular Expressions and Languages Questions and Answers || Regular Expressions and Languages MCQ Questions and Answers || Regular Expressions and Languages GK Questions and Answers || Regular Expressions and Languages GK MCQ Questions || Regular Expressions and Languages Multiple Choice Questions and Answers || Regular Expressions and Languages GK || GK on Regular Expressions and Languages || Theory of Computation Questions and Answers || Theory of Computation MCQ Questions and Answers || Theory of Computation GK Questions and Answers || GK on Theory of Computation

Regular Expressions and Languages Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications