Regular Expressions in Theory of Computation: Rules, Conversions and Worked Examples

Regular expressions look compact, but one misplaced star or suffix changes the language completely. Write 0*10*10* where the language needs 0*10*100* and the pattern silently admits 11, a string carrying no trailing zero at all. The habit that prevents this is to fix what each symbol denotes, then attack the candidate with the shortest strings that ought to fail.

What a regular expression denotes

Fix the alphabet Σ = {0,1}. A regular expression r denotes a language L(r), which is a set of strings. The three base cases are:

• L(∅) = ∅: no string is present.

• L(ε) = {ε}: the language contains the one empty string, whose length is 0.

• L(0) = {0}: the language contains the one-character string 0.

Do not confuse ε with ∅. One is a string; the other is an empty language.

The core operations follow directly from languages. Union r|s chooses a string from either language. Concatenation rs joins one string from L(r) to one from L(s). Kleene star r* allows zero or more copies, so it always includes ε. The forms r+ = rr* and r? = ε|r are shorthand, not extra expressive power in classical Theory of Computation.

Precedence is star first, concatenation second, union last. Thus 0|10* means {0} ∪ {1,10,100,...}. In contrast, (0|1)0* also contains 00. Parentheses make intended grouping explicit.

Build a regular expression from a language condition

Construct an expression over Σ = {0,1} for all strings that contain exactly two 1s and end in 0.

Every valid string has five forced blocks: any leading zeros, the first 1, any zeros between the two 1s, the second 1, and at least one trailing zero. Writing the required trailing zero separately gives:

0*10*100*

Check it against boundary strings:

• 110 is accepted: both earlier zero runs are empty, and the last 0 is required.

• 0010100 is accepted as 00 | 1 | 0 | 1 | 0 | 0.

• ε is rejected, while 00010 has only one 1.

• 101 does not end in 0, and 1110 has three 1s.

The tempting expression 0*10*10* is wrong because it accepts 11. It makes every trailing zero optional.

This suggests a reusable method: identify forced events, put unrestricted runs between them, write required occurrences literally, then attack the expression with the shortest boundary strings.

Convert a regular expression to an NFA and then a DFA

Regular expressions, right-linear grammars, NFAs, and DFAs describe the same regular languages. For r = (0|1)*01, the language of binary strings ending in 01, an exact right-linear grammar is S -> 0S | 1S | 0A and A -> 1, with start symbol S. Thompson's construction turns any expression into an NFA mechanically, one fragment per operator, but it pays for that generality with ε-transitions and spare states, and a short expression reads straight off its parts.

The star (0|1)* needs one state that can absorb any symbol, so let n0 be the start state with self-loops on 0 and 1. The suffix 01 adds two moves: on 0 from n0 to n1, then on 1 from n1 to the accepting state n2. There are no other transitions. The nondeterminism sits entirely in that second 0 out of n0, where the machine guesses that the zero it is reading opens the final 01 rather than being swallowed by the star. One correct guess is enough.

On 1101, the branch at n0 reads the prefix 11. After the next 0, one branch remains at n0 and another reaches n1. The final 1 takes the second branch to n2, so the NFA accepts. On 1010, no branch is at n2 after the last symbol, so it rejects.

Subset construction produces three DFA states. A={n0} is the start, B={n0,n1}, and C={n0,n2} is the only accepting state.

Subset construction in general considers every subset of NFA states, and only the reachable ones survive, which is why three are enough here. Finite Automata: DFA vs NFA and Subset Construction comes at the same construction from the machine side, with the 5-tuple definition and the 2^n bound on reachable subsets.

Equivalence laws, Arden's theorem and closure

Useful laws include r|∅ = r, rε = r, r|r = r, r* = ε|rr*, and (r*)* = r*. Each follows from the set of strings denoted, not from visual resemblance. For example, 0*1* is not equivalent to (0|1)*; the shortest counterexample is 10.

To convert an automaton back to an expression, use state elimination or language equations. A start-and-accept state with an a self-loop gives X = aX | ε. Since ε is not in the coefficient language {a}, Arden's theorem yields X = a*. That condition matters when applying the theorem.

Regular languages are closed under union, concatenation, and star directly through expressions. DFA constructions establish closure under intersection, complement, and difference. Over {0,1}, the complement of strings ending in 01 contains ε, 1, and 1010, but excludes 01 and 1101.

Know what classical regular expressions cannot express

Classical regular expressions cannot describe {0^n1^n | n >= 0} or all binary palindromes. A finite automaton cannot retain an unbounded count, or remember an unbounded first half for later comparison.

Programming regex libraries may add features such as backreferences that recognise some non-regular patterns. Those extensions do not change what a classical regular expression means in an automata-theory question. Regular Expressions and the Pumping Lemma explains the standard proof technique. The pumping lemma is normally used to prove non-regularity; pumping a few selected strings does not prove regularity.

Common traps and a reliable checking routine

Remember that L(ε)={ε}, L(∅)=∅, and ∅*={ε}. Also, 1* accepts ε, while 1+=11* requires at least one 1. Test ε first whenever * or ? appears.

Keep exact match, suffix, and substring separate. Exact 01 is 01; strings ending in 01 are (0|1)*01; strings containing 01 anywhere are (0|1)*01(0|1)*. The string 010 separates the last two because it contains 01 but does not end in 01.

Textual difference also does not imply language difference: 0|1 and 1|0 denote the same language. A reliable check has four steps: parse by precedence, test ε, test the shortest accepted and rejected boundary strings, then search for one counterexample before attempting a formal proof.

How GATE-style and interview questions test the idea

Typical tasks ask you to construct an expression, select equivalent expressions, trace an automaton, count fixed-length strings, or decide whether a language is regular. Try these before reading the answers:

1. Does 0*10*100* accept 100100 and 10101?

2. Which DFA state (from the transition table above) is reached on 1101?

3. How many length-5 binary strings end in 01?

Answers: 100100 is accepted; 10101 is rejected because it has three 1s and ends in 1. The DFA finishes in accepting state C. For length 5, the first three positions are free and the last two are fixed, so the count is 2^(5-2) = 8.

Interviews compress the same skill into one exchange: you are asked for a pattern, then immediately asked for a string that breaks it. State the expression, then volunteer the boundary cases you already tested, for example that 0*10*100* rejects 11 for want of a trailing zero and 101 for ending in 1.

The GATE category collects the wider preparation route for these topics, and Theory of Automata sits inside the subject-wise coverage of the GATE Test Series.

The short version and next step

A regular expression denotes a language. Union, concatenation, and star are its core operators. Every classical regular expression can be converted to an NFA and DFA, and only regular languages are expressible in this model. Before doing algebra, test a candidate against boundary strings.

Now remove the required final symbol from the two-1s expression built earlier. Derive 0*10*10*, then verify that it accepts 11 and 100100 but rejects 10 and 10101. After that, redraw the DFA from its transition table without looking at the diagram.

For a structured route through GATE CS topics, continue with GATE Guidance by Sanchit Sir.