letting P::: = I, P 3 = 011
140 J;! Theory of Computer Science
Solution
(a) If w is in L, then either (a) w does not contain any 0, or (b) it contains
a °preceded by 1 and followed by 11. So w can be written as
H' 1w::: ... w n , where each Wi is either 1 or OIl. So L is represented
by the Le. (1 + 011)*.
(b) R = A + PtPt, where P 1 = 1*(011)*
= p{
using 1 9
= (1*(011)*)*
= W:::*P J ')*
using III
= (1 + 011)*
EXAMPLE 5.4
Prove (1 + 00*1) + (1 + 00*1)(0 + 10*1)* (0 + 10*1) =0*1(0 + 10*1)*.
Solution
L.R.S. = (1 + 00*1) (A + (0 + 10*1)* (0 + 10*1)A using 1 1 :::
= (1 + 00*1) (0 + 10*1)*
using 1 9
= (A + 00*)1 (0 + 10*1)*
using 1 1 ::: for 1 + 00*1
= 0*1(0 + 10*1)*
using 1 9
= R.H.S.
5.2 FINITE AUTOMATA AND REGULAR EXPRESSIONS
In this section we study regular expressions and their representation.
5.2.1 TRANSITION SYSTEM CONTAINING A-MOVES
The transition systems can be generalized by permitting A-transitions or
A-moves which are associated with a null symbol A. These transitions can
occur when no input is applied. But it is possible to convert a transition system
with A-moves into an equivalent transition system without A-moves. We shall
give a simple method of doing it with the help of an example.
Suppose we want to replace a A-move from vertex V1 to vertex V2' Then
we proceed as follows:
Step 1 Find all the edges starting from v:::.
Step 2 Duplicate all these edges stalting from V1' without changing the edge
labels.