A.4 Regular Languages, Regular Expressions and Finite-state Machine

Regular languages (RL) are specified by a Regular Expression (RE), a Regular Grammar (RG) or indirectly by its acceptor, a Finite-state Machine (FSM).

A.4.1 Regular Languages

Three basic set operations of union, intersection and closure are used to define a new language from an existing one. If we start with a finite vocabulary VT and build a language using only these operations, we get a Regular Language and the formula by which it is specified is called Regular Expression.

Recursive Definition of RL

A RE denotes a RL, which is also called its valuation or meaning, see Table A.3.


Table A.3 Recursive definition of a regular expression and regular language

RE Valuation ...

Get Compilers: Principles and Practice now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.