21. Give a general method by which any regular expression r can be changed
into r such that (L (r)) R = L(r)) R =L( )
22. Prove rigorously that the expressions in Example 3.6 do indeed denote the
specified language.
23. For the case of a regular expression r that does not involve λ or Ø, give a
set of necessary and sufficient conditions that r must satisfy if L(r) is to be
infinite.
24. Formal languages can be used to describe a variety of two-dimensional
figures. Chain-code languages are defined on the alphabet Σ = {u, d, r, l},
where these symbols stand for unit-length straight lines in the directions up,
down, right, and left, respectively. An example of this notation is urdl,
which stands for the square with sides of unit length. Draw pictures of the
figures denoted by the expressions (rd)*, (urddru)*, and (ruldr)*.
25. In Exercise 24, what are sufficient conditions on the expression so that the
picture is a closed contour in the sense that the beginning and ending points
are the same? Are these conditions also necessary?
26. Find an nfa that accepts the language L (aa* (a + b)).
27. Find a regular expression that denotes all bit strings whose value, when
interpreted as a binary integer, is greater than or equal to 40.
28. Find a regular expression for all bit strings, with leading bit 1, interpreted
as a binary integer, with values not between 10 and 30.
3.2 Connection between Regular Expressions and
Regular Languages
As the terminology suggests, the connection between regular languages and
regular expressions is a close one. The two concepts are essentially the same; for
into r such that (L (r)) R = L(r)) R =L( )
22. Prove rigorously that the expressions in Example 3.6 do indeed denote the
specified language.
23. For the case of a regular expression r that does not involve λ or Ø, give a
set of necessary and sufficient conditions that r must satisfy if L(r) is to be
infinite.
24. Formal languages can be used to describe a variety of two-dimensional
figures. Chain-code languages are defined on the alphabet Σ = {u, d, r, l},
where these symbols stand for unit-length straight lines in the directions up,
down, right, and left, respectively. An example of this notation is urdl,
which stands for the square with sides of unit length. Draw pictures of the
figures denoted by the expressions (rd)*, (urddru)*, and (ruldr)*.
25. In Exercise 24, what are sufficient conditions on the expression so that the
picture is a closed contour in the sense that the beginning and ending points
are the same? Are these conditions also necessary?
26. Find an nfa that accepts the language L (aa* (a + b)).
27. Find a regular expression that denotes all bit strings whose value, when
interpreted as a binary integer, is greater than or equal to 40.
28. Find a regular expression for all bit strings, with leading bit 1, interpreted
as a binary integer, with values not between 10 and 30.
3.2 Connection between Regular Expressions and
Regular Languages
As the terminology suggests, the connection between regular languages and
regular expressions is a close one. The two concepts are essentially the same; for