PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q2

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Regular Expressions & Equivalence with Finite Automata

Question

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 :

  1. 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, .
  2. 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 .
  3. 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.

All past exam questions for Theory of Computation