Ling 501, Fall 2004: Regular languages

For an illustration of how concatenation and union work to build regular languages, click here.

Regular expressions

A regular expression is a compact notation for representing a particular regular language, using concatenation, union and unbounded repetition.

Notational conventions for regular expressions

The notations that we use for regular expressions include the following repetition operators.

• "Kleene star": s* = {sⁿ : n ³ 0} = s+ È {e} = {e, s, s², ...}
• "Kleene plus": s+ = {sⁿ : n > 0} = {s, s², ...}
• "Optional": s? = {sⁿ : 0 £ n £ 1} = {e, s}

Here is the notation for union.

• "Pipe": s | t = {x : x = s or x = t} = {s, t}

We can take the Kleene plus and pipe operators as the basic notations, and define the Kleene star and optionality operators in terms of them as follows. However, we allow the use of all four operators in homework answers.

• s* = s+ | e.
• s? = s | e.

Scope of string operators

The scope of any string operator can be indicated explicitly by parentheses. Without parentheses, the scope of ⁿ, +, * and ? is the string to their immediate left, and the scope of | is the strings to its immediate left and right. Here are some examples.

• st² = stt
• (st)² = stst
• st+ = {st, st², ...}
• (st)+ = {st, (st)², ...}
• st* = {s, st, st², ...}
• (st)* = {e, st, (st)², ...}
• st? = {s, st}
• (st)? = {e, st}
• s | t = (s | t) = {s, t}
• s* | t* = {e, s, t, s², t², ...}
• (s | t)* = {e, s, t, s², st, ts, t², ...}

A regular expression problem

Let R the language consisting of the set of rational numbers in binary notation.

• The vocabulary S of R is {-, /, 0, 1}.
• Some well-formed expressions: {0, 1, 10, 11, 100, -1, -10, 1/10, 101/10, 0/1, -1/100, -11/10}.
• Some ill-formed expressions: {e, -, -0, 1-, 1-1, /, /1, 1/, 0/0, 100/0, 1/-1, 01, 00001, -01, 01/1, 1/01, 1/1/1}.

Write a regular expression for R. (Hint: First formulate a set of rules for the "use" of the members of S. Then "translate" these into regular-expression notation.)

Some rules regarding the composition of members of R.

The minus sign:

• Can occur at most once.
• Can only occur at the beginning of the string.

The division sign:

• Can occur at most once.
• Can only occur between two numerals (call the first one the 'numerator', the second one the 'denominator').

Zero:

• Can occur as the only symbol in a string, or as the only symbol in the numerator. Otherwise it cannot occur at the beginning of a numeral (no 'leading zeroes').
• Cannot occur by itself as the denominator.

One:

• Must occur as the first symbol in a numeral other than '0'.
• Following an initial '1', zeroes and ones can occur in any combination.

Forming the regular expression

• Start with: (0 | -? 1 (0 | 1)*) [for whole numbers or numerators of fractions]

• Continue with: (/ 1 (0 | 1)*)? [for denominators]
• The entire regular expression is: (0 | -? 1 (0 | 1)*) (/ 1 (0 | 1)*)?

Regular grammars

• N is a finite nonempty set of nonterminal symbols (categories) {A₁, ..., A_n};
• S is a finite nonempty set of terminal symbols (words) {a₁, ... a_m}, where N Ç S = Æ and N È S = V;
• S Î N is the start (axiom) symbol;
• P is a finite set of productions (rules) of the form A ® x B or A ® x (right-linear), or of the form A ® B x or A ® x (left-linear) where A, B Î N and x Î S*.

Derivations and generated languages

A derivation of the string s in a regular grammar RG is a sequence of lines starting with A₀ and ending with s, where s Î V*. Each line in the derivation except the first is formed from the previous one by replacing a nonterminal symbol A by the right hand side of a rule whose left hand side is A. If s Î S*, the derivation is said to be terminated. The language generated by RG is the set L consisting of strings that have terminated derivations.

Example

Here is a regular grammar G for the regular language consisting of the rational numbers in binary notation. (The productions are numbered for ease of reference.)

G = {N, S, S, P}, where:

• N = {A, B, C, D, E, F}
• S = {0, 1, -, /}
• S= A
• P =

Derivation of the string -10/11: