Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Theory of Computation  >  Previous Year Questions: Regular Expression

Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Q1: Let M be the 5-state NFA with ϵ-transitions shown in the diagram below:
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
Which one of the following regular expressions represents the language accepted by M ?  (2024 SET-2)
(a) (00)* + 1(11)*
(b) 0* + (1 + 0(00)*)(11)*
(c) (00)* + (1 + (00)*)(11)*
(d) 0 + + 1(11)* + 0(11)*
Ans: 
(b)
Sol:

Option A. here it is showing that even no of O's is accepted with odd no of 1's but if we try to find the solution for 00111 we cannot find with the help of given NFA
Option C. Here also if we will take an example for the string 00000 we won't be able to find in the given option but this string is accepted by the NFA
Option D. Here empty string is not present. Atleast 0 is always present. Hence this solution is also not correct.
Correct Answer is: B

Q2: Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?  (2024 SET-2)
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
(a) 0*1(0 + 10*1)*
(b) 0*(10*11)*0*
(c) 0*1(010*1)*0*
(d) 0(1 + 0*10*1)*0*
Ans: 
(a)
Sol:

The given DFA accepts all & only binary strings containing Odd number of 1's.
So, option A is correct regular expression.
Option B Counter-Example: Generates empty string.
Option C Counter-Example: Doesn't generate 10011.
Option D Counter-Example: Doesn't generate 1.
WHY Option A: Go to the final state by reading 0*1, then stay in the final state by making either loop 0 or loop 10*1 in any order, any number of times. So, 0*1(0 + 10*1)* is the correct regular expression.

Q3: Consider the following two regular expressions over the alphabet {0, 1}:
r = 0* + 1*
S = 01* + 10*
The total number of strings of length less than or equal to 5, which are neither in r nor in s, is______  (2024 SET-1)
(a) 44
(b) 55
(c) 66
(d) 33
Ans:
Sol:

1. zero length string epselon can be formed using r.
2. all string with length 1 {a,b} can be formed using r.
3. in string with length 3, total 8 strings can be formed as there is three digit and for every digit we can select either 0 or 1, so 2 x 2 x 2 = 8.
Now As per RE r = {000, 111} and s = {011, 100) will be formed using RE r and s.
so strings of length 3 not present in both RE will be = 8 - 4 = 4.
4. For length 4, Similarly as 3rd steps
total string = 2 x 2 x 2 x 2 = 16
total strings not present in r and s = 16 - 4{0000, 1111, 0111, 1000} = 12.
5. For length 5, Similarly as 3rd steps
total string = 2 x 2 x 2 x 2 x 2 = 32
total strings not present in r and s = 32 - 4{00000, 11111, 01111, 10000} = 28.
So total string of length less than equal to 5 which are not present in both RE r and s will be 4 + 12 + 28 = 44(Option A).

Q4: Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:
letter → A - Za - z
digit → [0 - 9]
id → letter(letter | digit)*
Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)  (2023)

Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
(a) A
(b) B
(c) C
(d) D
Ans:
(c)
Sol:

The regular expression is given as letter (letter + digit)*.
This regular expression accepts the strings of one occurrence of a letter followed by any occurrence of letter and digits, such as (letter, letter.letter,letter.digit,letter.digit.digit..∞)
Option (A) This is wrong because it also accepts empty string that is ϵ.
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
Option (B):
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE) 
This is wrong because it accepts strings like (letter), (letter.letter) ...(letter.digit), (letter.digit.digit), but it will not accepts the strings like (letter.digit.letter).
Option (C): It is the correct option. it will accepts all the strings of letter (letter + digit)*
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
Option (D):
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
it is wrong. it RE is (letter(letter. digit)*)
and it will accept strings like (letter), (letter. letter. digit). (letter. letter. digit. letter. digit).....∞
it will not accepts strings like (letter. letter), (letter. digit) etc.

Q5: Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states (s, p, q, r), with s being the start state and p being the only final state.
Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
Which one of the following regular expressions correctly describes the language accepted by A?  (2023)
(a) 1(0*11)*
(b) 0(0 + 1)*
(c) 1(0 + 11)*
(d) 1(110*)*
Ans:
(c)
Sol:

The given finite automata generate string like
(1, 10, 111, 100, 11111, 1011, 1110, 10000, 101111, 10011...∞).
Start with 1 to reach the final state after that we have 2 choices as (0 + 11)*.
∴ R.E. = 1(0 +11)*
Option (A): it is wrong because it will not generate strings like 10
Option (B): it is wrong because it will generate 0 which is rejected in the given DFA.
Option (D): it is wrong because it will not generate strings like 10, 100.
Option (C) is correct.

Q6: Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ϵ is divisible by three.  (2021 SET-2)
(a) (0 + 1(01*0)*1)*
(b) (0 + 11 + 10(1 + 00)*01)*
(c) (0*(1(01*0)*1)*)*
(d) (0 + 11 + 11(1 + 00)*00)*
Ans: 
(a, b and c)
Sol:

Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)
After this dfa is constructed, then by state elimination method we will directly get regular expression same as option A → (0 + 1(01*0)*1)* and now as per property (a + b)* = (a*b*)*, considering a as 0 and b as 1(01*0)1 we will get option c) (0* (1(01*0)1)*)* and now for option b and d we will check directly by checking the strings that will be accepted and from that we can observe that 1001(i.e.9) will not be accepted in option d)
Hence the ans A,B,C

Q7: Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?  (2020)
(a) ((0 + 1)*1(0 + 1)*1)*10*
(b) (0*10*10*)*0*1
(c) 10* (0*10*10*)*
(d) (0*10*10*)*10*
Ans: 
(d)
Sol:

The regular expression should generate all possible binary strings with odd number of 1's and doesn't generate the other strings.
Option 1: Incorrect
Regular Expression: ((0 +1)*1(0 + 1)*1)*10*
String: 11110
It can generate strings (11110) with even number of 1's also
Option 2: Incorrect
Regular Expression: (0*10*10*)*0*1
It will generate string only ending with '1'
String: 1110
It cannot generate '1110' substring.
Option 3: Incorrect
Regular Expression: 10*(0*10*10*)*
It will generate string only starting with '1'
String: 0111
It cannot generate '0111' substring.
Option 4: Correct
Regular expression: 0*(10*10*)*10*
It will generate all possible binary strings with odd number of 1's and doesn't generate the other strings.

Q8: Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?  (2016 SET-1)
(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
Ans:
(b)
Sol:

Set of all binary strings having two consecutive Os and two consecutive 1s
Anything 00 Anything 11Anything + Anything 11 Anything 00 Anything
(0 + 1)*00(0 + 1)*11(0 + 1)* + (0 + 1)*11(0 + 1)*00(0 + 1)*
And it is same after taking common.
(0 + 1)*(00(0 + 1)*11 + 11(0 + 1)*00)(0 + 1)*
So, option B is answer.
Neither they said Both are immediate nor they give a predefined order, so it should be as above

Q9: The length of the shortest string NOT in the language (over ∑= {a, b}) of the following regular expression is________.  (2014 SET-3)
a*b* (ba)* a*

(a) 1
(b) 2
(c) 3
(d) 4
Ans: 
(c)
Sol:
 
R = a*b*(ba)*a*
for finding shortest string that is not in language it is better to look strings of length 0, then of
length 1 and so on
length0{ϵ} is in L
length1{a, b} all belong to L
length2{aa, ab, ba, bb} all belong to L
length3{aaa, aab, aba, abb, baa, bab, bba, bbb} bab does not belong to L

Q10: Let L = {w ∈ (0+1)* / w has even number of 1s), i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?  (2010)
(a) (0*10*1)*
(b) 0*(10*10*)*
(c) 0*(10*1)*0*
(d) 0*1(10*1)*10*
Ans: (b)
Sol:
A. -If the string contains a 1, it must end in a 1 hence cannot generate all bit strings with even number of 1's (eg, 1010)
B. - is the answer
C. - between the second and third 1's a 0 is not allowed (eg, 011011)
D. - 00 is not allowed, zero is an even number.

The document Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on Previous Year Questions: Regular Expression - Theory of Computation - Computer Science Engineering (CSE)

1. What is a regular expression?
Ans. A regular expression is a sequence of characters that define a search pattern, used for pattern matching within strings.
2. How are regular expressions used in computer science engineering?
Ans. Regular expressions are used in various applications such as text processing, searching, and data validation in computer science engineering.
3. What are some common metacharacters used in regular expressions?
Ans. Some common metacharacters used in regular expressions include '.', '*', '+', '?', '^', '$', '|', '()', '[]', and '{}'.
4. How can regular expressions be used to validate user input in a form?
Ans. Regular expressions can be used to define a specific pattern that user input must match, ensuring that the data entered in a form follows the desired format.
5. Can regular expressions be used in programming languages other than Python?
Ans. Yes, regular expressions are supported in many programming languages such as JavaScript, Java, C#, and Perl, allowing for consistent pattern matching across different platforms.
18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

shortcuts and tricks

,

mock tests for examination

,

Summary

,

Exam

,

Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)

,

Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)

,

practice quizzes

,

Extra Questions

,

Objective type Questions

,

Previous Year Questions: Regular Expression | Theory of Computation - Computer Science Engineering (CSE)

,

MCQs

,

Sample Paper

,

pdf

,

Semester Notes

,

Important questions

,

study material

,

Previous Year Questions with Solutions

,

Viva Questions

,

ppt

,

Free

,

video lectures

,

past year papers

;