16 REGULAR LANGUAGES- Construct a regular expression for the set of all strings over alphabet
{( $( i)( a)*( !J( a);( i)( i+( i)}
that represent correct subtractions. For example,- Show that for any regular language L, Lodd = {z E L ] 1x1 = odd} and
implies that string(I)(Y)(l)(b)
is in the set.L ezIen = {d: E L 1 1x1 = even} are regular.- Show that if L is a regular language, then Lā = {u I 31, uv E L} is
regular. - Suppose h : C + IT is a mapping satisfying h(zy) = h(z)h( y) for any
x,y E c. Show that if A is a regular set over C, then h(A) = {h(z) I
II= E A} is a regular set over I?. Conversely, if B is a regular set over
r, then h-l(B) = {z E C I h(z) E B} is a regular set over C. [Hint:
Prove by induction.]
1.3 Graph Representations for Regular Expressions
A directed graph (or, digruph) is a pair of sets (V, E) such that each element in
E is an ordered pair of elements in V. The elements in V are called vertices,
and the elements in E are called edges. An edge (u, v) is directed, meaning
that it originates at u and goes to v. For this reason, (u, v) is said to be
an in-edge to v and an out-edge from u. A loop is an edge which starts and
ends at the same vertex; that is, it is both an in-edge and an out-edge for
the same vertex. We often draw a diagram for a graph with a small circle
representing a vertex and an arrow from circle u to circle v representing an
edge (u, v). Figure 1.2 shows a digraph G = (V, E) where V = {a, b, c, d} and
E = -@,a), (O), (b, b), (kc), (v), (CGW
A path is a finite sequence of vertices, (VI, 212, s l l , vk), such that there exists
an edge from vi to vi+1 for every i = 1,2, l l l , k - 1. For example, in Figure
1.2, (a, b, c, d) is a path, but (a, c, d) is not a path because no edge exists from
a to c. A path starting and ending at the same vertex is called a cycle.