The given FSM :is equivalent to :

The machine is equivalent to 0*1 (0 + 1).Trace the paths from the start state a1 to the final state a3. The self-loop on a1 reads any number of 0s, giving 0*. The only way out of a1 is on 1, giving 1. From a2 one more symbol, 0 or 1, reaches a3, giving (0 + 1). So the language is 0*1(0 + 1).1*0(0 + 1) swaps the roles of 0 and 1. 01*(0 + 1) and 00*(0 + 1) would need a loop on 1 or require at least one leading 0, neither of which the machine has.

Regular Expressions and Languages Questions and Answers

Q: Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

The regular expression is \((0+1)^{*}(00(0+1)^{*}11 + 11(0+1)^{*}00)(0+1)^{*}\).A string with both a 00 and a 11 has one of them occurring first. So it is: anything, then 00, then anything, then 11, then anything; or the same with 11 first. The middle \((0+1)^{*}\) lets the two pairs be separated, and the outer ones allow any prefix and suffix. That is exactly this expression.The 0011/1100 option forces the pairs to be adjacent, missing strings such as 001011, where the pairs are separated. The option joined by '+' with \((0+1)^{*}00(0+1)^{*}\) accepts strings with only 00 or only 11. The last option forces the string to start and end with the pairs, missing 100110.

Q: Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

The equivalent expression is \(0^{*}1(0 + 10^{*}1)^{*}\).Only 1s change the state, and each 1 moves between the two states, so the DFA accepts exactly the strings with an odd number of 1s. \(0^{*}1\) reads any 0s and the first 1, reaching the accepting state. From there, \((0 + 10^{*}1)^{*}\) repeatedly either reads a 0 (staying put) or reads a 1, any 0s, and a 1 (leaving and coming back), so it always returns to the accepting state and can generate every such continuation.\(0^{*}(10^{*}11)^{*}0^{*}\) accepts the empty string, which has no 1s. \(0^{*}1(010^{*}1)^{*}0^{*}\) cannot generate 11 followed by 1 (that is, 111), and \(0(1 + 0^{*}10^{*}1)^{*}0^{*}\) insists on a leading 0 and accepts 0 alone.

Q: Write an Regular expression :Starting with 0's or 1's ending with '01' is equivalent to :

The expression is (0 + 1)* 01.(0 + 1)* matches any string of 0s and 1s, including the empty string, so it covers whatever comes first. Appending 01 forces the string to end with 0 followed by 1. Every binary string ending in 01 can be split this way, and every string the expression generates ends in 01.The other options fix the wrong ending: (0 + 1)* 11 ends in 11, (0 + 1)* 00 in 00, and (0 + 1)* 10 in 10.

Q: Which of the following languages are denoted/represented by the regular expression :\(((0+1)(0+1)^{*})^{*}\ 00\ (0+1)^{*}\)(i) The language contains strings over 0's and 1's with at least one pair of consecutive zeros.(ii) The language contains strings over 0's and 1's with strings starting with either 0 or 1 and may end with 0 or 1.(iii) The language contains strings over 0's and 1's with number of 0's to be more than number of 1's.

The answer is (i) and (ii) only.The prefix \(((0+1)(0+1)^{*})^{*}\) can produce any string of 0s and 1s, including the empty string, so it is equivalent to \((0+1)^{*}\). The whole expression is therefore \((0+1)^{*}\,00\,(0+1)^{*}\): any binary string that contains 00 somewhere, that is, at least one pair of consecutive zeros (i). Such strings can begin and end with either symbol, as statement (ii) says, for example 1001 or 0010.Statement (iii) is false: 11001 contains 00 but has fewer 0s than 1s. So options including (iii) are wrong.

Q: Which of the following is correct statement ?(i) A language is a regular language if and only if it can be represented by a regular expression.(ii) A language is a regular if and only if it cannot be generated by a regular grammar.(iii) Every regular grammar is context free grammar.

Statements (i) and (iii) are correct, so the answer is (i) and (iii) only.Statement (i) is Kleene's theorem: a language is regular if and only if some regular expression describes it. Statement (iii) is true because a regular grammar's productions (a variable going to a terminal string optionally followed by one variable) are a special case of context-free productions, so every regular grammar is context-free.Statement (ii) is false: a language is regular if and only if it can be generated by a regular grammar. Options that include (ii), or that leave out (i), are wrong.

Q: Which among the following is not notated as infinite language ?

The one not notated as an infinite language is Factorial.The set of palindromes over an alphabet, the set of strings formed by a word followed by its reverse, and L = {ab}*, which contains the empty string, ab, abab and so on, are all standard examples of infinite languages: each contains infinitely many strings.'Factorial' names a function on numbers, not a set of strings, so it is the one that is not written as an infinite language.

Q: Which of the following pairs of regular expressions are equivalent ?

The answer is All of the above: every pair is equivalent.\(1(01)^{*}\) and \((10)^{*}1\) both give 1, 101, 10101, ...: alternating strings that begin and end with 1.\(x(xx)^{*}\) and \((xx)^{*}x\) both give the strings of x of odd length: x, xxx, xxxxx, ...\(x^{+}\) and \(x^{+}x^{*+}\): since \((x^{*})^{+} = x^{*}\), the second is \(x^{+}x^{*} = x^{+}\), one or more x's.Because each of the three pairs describes the same language, no single pair is the whole answer.

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

A.\((0+1)^{*}0011(0+1)^{*} + (0+1)^{*}1100(0+1)^{*}\)
B.\((0+1)^{*}(00(0+1)^{*}11 + 11(0+1)^{*}00)(0+1)^{*}\)
C.\((0+1)^{*}00(0+1)^{*} + (0+1)^{*}11(0+1)^{*}\)
D.\(00(0+1)^{*}11 + 11(0+1)^{*}00\)

Exam Year(s)

GATE CS - 2016,

Answer: B

The regular expression is \((0+1)^{*}(00(0+1)^{*}11 + 11(0+1)^{*}00)(0+1)^{*}\).

A string with both a 00 and a 11 has one of them occurring first. So it is: anything, then 00, then anything, then 11, then anything; or the same with 11 first. The middle \((0+1)^{*}\) lets the two pairs be separated, and the outer ones allow any prefix and suffix. That is exactly this expression.

The 0011/1100 option forces the pairs to be adjacent, missing strings such as 001011, where the pairs are separated. The option joined by '+' with \((0+1)^{*}00(0+1)^{*}\) accepts strings with only 00 or only 11. The last option forces the string to start and end with the pairs, missing 100110.

Discuss in Forum

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

DFA with two states: the start state, not accepting, has a self-loop on 0 and goes to the accepting state on 1; the accepting state has a self-loop on 0 and returns to the start state on 1

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

Exam Year(s)

GATE CS - 2024,

Answer: A

The equivalent expression is \(0^{*}1(0 + 10^{*}1)^{*}\).

Only 1s change the state, and each 1 moves between the two states, so the DFA accepts exactly the strings with an odd number of 1s. \(0^{*}1\) reads any 0s and the first 1, reaching the accepting state. From there, \((0 + 10^{*}1)^{*}\) repeatedly either reads a 0 (staying put) or reads a 1, any 0s, and a 1 (leaving and coming back), so it always returns to the accepting state and can generate every such continuation.

\(0^{*}(10^{*}11)^{*}0^{*}\) accepts the empty string, which has no 1s. \(0^{*}1(010^{*}1)^{*}0^{*}\) cannot generate 11 followed by 1 (that is, 111), and \(0(1 + 0^{*}10^{*}1)^{*}0^{*}\) insists on a leading 0 and accepts 0 alone.

Discuss in Forum

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

(Figure: the automaton has a start state and two accepting states. From the start state, a goes to the first accepting state, which loops on b and returns to the start state on b; b goes to the second accepting state, which loops on a and returns to the start state on a.)

A.\(ab^{*}bab^{*} + ba^{*}aba^{*}\)
B.\((ab^{*}b)^{*}ab^{*} + (ba^{*}a)^{*}ba^{*}\)
C.\((ab^{*}b + ba^{*}a)^{*}(a^{*} + b^{*})\)
D.\((ba^{*}a + ab^{*}b)^{*}(ab^{*} + ba^{*})\)

Exam Year(s)

GATE CS - 2022,

Answer: D

The automaton's language is \((ba^{*}a + ab^{*}b)^{*}(ab^{*} + ba^{*})\).

Every run starts at the start state. A round trip through the upper state reads \(a\), any number of \(b\)s on its loop, then the \(b\) back: \(ab^{*}b\). A round trip through the lower state reads \(ba^{*}a\). A run may take any number of these round trips in any order, then must finish in an accepting state, either by \(a\) followed by \(b\)s (\(ab^{*}\)) or by \(b\) followed by \(a\)s (\(ba^{*}\)).

Option A allows exactly one round trip, so it misses even the single letter a. Option B never mixes the two kinds of round trip, so it misses abbaa, which the automaton accepts as the round trip ab followed by the finish baa. Option C accepts the empty string and strings such as aa, but the start state is not accepting and has no way to read aa.

Discuss in Forum

The given FSM :

Finite state machine: Start arrow into state a1, which has a self-loop labelled 0; a1 goes to a2 on 1; a2 goes to the final state a3 (double circle) on 0 or 1

is equivalent to :

A.1*0 (0 + 1)
B.0*1 (0 + 1)
C.01* (0 + 1)
D.00* (0 + 1)

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: B

The machine is equivalent to 0*1 (0 + 1).

Trace the paths from the start state a₁ to the final state a₃. The self-loop on a₁ reads any number of 0s, giving 0*. The only way out of a₁ is on 1, giving 1. From a₂ one more symbol, 0 or 1, reaches a₃, giving (0 + 1). So the language is 0*1(0 + 1).

1*0(0 + 1) swaps the roles of 0 and 1. 01*(0 + 1) and 00*(0 + 1) would need a loop on 1 or require at least one leading 0, neither of which the machine has.

Discuss in Forum

Write an Regular expression :

Starting with 0's or 1's ending with '01' is equivalent to :

A.(0 + 1)* 11
B.(0 + 1)* 00
C.(0 + 1)* 01
D.(0 + 1)* 10

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: C

The expression is (0 + 1)* 01.

(0 + 1)* matches any string of 0s and 1s, including the empty string, so it covers whatever comes first. Appending 01 forces the string to end with 0 followed by 1. Every binary string ending in 01 can be split this way, and every string the expression generates ends in 01.

The other options fix the wrong ending: (0 + 1)* 11 ends in 11, (0 + 1)* 00 in 00, and (0 + 1)* 10 in 10.

Discuss in Forum

Which of the following languages are denoted/represented by the regular expression :

\(((0+1)(0+1)^{*})^{*}\ 00\ (0+1)^{*}\)

(i) The language contains strings over 0's and 1's with at least one pair of consecutive zeros.
(ii) The language contains strings over 0's and 1's with strings starting with either 0 or 1 and may end with 0 or 1.
(iii) The language contains strings over 0's and 1's with number of 0's to be more than number of 1's.

A.(ii) and (iii) only
B.(iii) only
C.(i) and (ii) only
D.(i) and (iii) only

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The answer is (i) and (ii) only.

The prefix \(((0+1)(0+1)^{*})^{*}\) can produce any string of 0s and 1s, including the empty string, so it is equivalent to \((0+1)^{*}\). The whole expression is therefore \((0+1)^{*}\,00\,(0+1)^{*}\): any binary string that contains 00 somewhere, that is, at least one pair of consecutive zeros (i). Such strings can begin and end with either symbol, as statement (ii) says, for example 1001 or 0010.

Statement (iii) is false: 11001 contains 00 but has fewer 0s than 1s. So options including (iii) are wrong.

Discuss in Forum

Which of the following is correct statement ?

(i) A language is a regular language if and only if it can be represented by a regular expression.
(ii) A language is a regular if and only if it cannot be generated by a regular grammar.
(iii) Every regular grammar is context free grammar.

A.(i) only
B.(i) and (ii) only
C.(i) and (iii) only
D.(iii) only

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

Statements (i) and (iii) are correct, so the answer is (i) and (iii) only.

Statement (i) is Kleene's theorem: a language is regular if and only if some regular expression describes it. Statement (iii) is true because a regular grammar's productions (a variable going to a terminal string optionally followed by one variable) are a special case of context-free productions, so every regular grammar is context-free.

Statement (ii) is false: a language is regular if and only if it can be generated by a regular grammar. Options that include (ii), or that leave out (i), are wrong.

Discuss in Forum

Give regular expression for the language that contains all strings with at least one occurrence of each symbol in Σ = {a, b, c},.

A.(a + b + c)* abc (a + b + c)*
B.(a + b + c)* a (a + b + c)* b (a + b + c)* c (a + b + c)*
C.(a + b + c)* a (a + b + c)* b (a + b + c)* c
D.a (a + b + c)* b (a + b + c)* c (a + b + c)*

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: B

Of the options, the key's answer is (a + b + c)* a (a + b + c)* b (a + b + c)* c (a + b + c)*.

It allows any symbols before, between and after one a, one b and one c, so every string it matches contains all three symbols.

The other options are more restrictive. The first needs the substring abc, missing strings such as acbbc. The third must end in c, and the fourth must begin with a.

Strictly, this expression only matches strings in which some a comes before some b, which comes before some c, so a string such as cba is missed; a complete expression would combine all six orders. The paper's option set does not include that, and B is the most general of the four.

Discuss in Forum

Which among the following is not notated as infinite language ?

A.Palindrome
B.Reverse
C.Factorial
D.L={ab}*

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: C

The one not notated as an infinite language is Factorial.

The set of palindromes over an alphabet, the set of strings formed by a word followed by its reverse, and L = {ab}*, which contains the empty string, ab, abab and so on, are all standard examples of infinite languages: each contains infinitely many strings.

'Factorial' names a function on numbers, not a set of strings, so it is the one that is not written as an infinite language.

Discuss in Forum

10.

Which of the following pairs of regular expressions are equivalent ?

A.\(1(01)^{*}\) and \((10)^{*}1\)
B.\(x(xx)^{*}\) and \((xx)^{*}x\)
C.\(x^{+}\) and \(x^{+}x^{*+}\)
D.All of the above

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: D

The answer is All of the above: every pair is equivalent.

\(1(01)^{*}\) and \((10)^{*}1\) both give 1, 101, 10101, ...: alternating strings that begin and end with 1.
\(x(xx)^{*}\) and \((xx)^{*}x\) both give the strings of x of odd length: x, xxx, xxxxx, ...
\(x^{+}\) and \(x^{+}x^{*+}\): since \((x^{*})^{+} = x^{*}\), the second is \(x^{+}x^{*} = x^{+}\), one or more x's.

Because each of the three pairs describes the same language, no single pair is the whole answer.

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