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 books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
