Past exam question: 2082 Chaitra (Regular), Q2
Open in the Padhaiko appQuestion
Write regular expression for the language which generates the string containing odd number of 1 followed by even number of 0 or even number of 0 followed by odd number of 1 over .
Solution
Analysis of Sub-Languages and Building Regular Expressions: The language is the union of two disjoint structural patterns over alphabet :
- Odd number of 1s followed by an even number of 0s ():
- A block containing an odd number of s is expressed by or .
- A block containing an even number of s is expressed by (standard formal language definition where occurrences is an even count: ). If strictly non-zero even count is required, .
- Thus, .
- Even number of 0s followed by an odd number of 1s ():
- A block of even number of s followed by an odd number of s is expressed by .
- Combined Union:
Equivalently, factoring the odd block of ones:
Answer:
The regular expression is , representing strings with an odd count of s followed by an even count of s, or an even count of s followed by an odd count of s.