Introduction to Automata Theory, Formal Languages and Computation

5

Regular Expression

Introduction

Regular expression, in short RE, is the language part of the type 3 grammar, which is called regular grammar. RE is accepted by the machine called finite automata (FA). RE was first proposed by an American mathematician Stephen Kleene as a notion of describing the algebra of a regular set. Later on, Ken Thompson used the RE in early computer text editor ‘QED’ and Unix editor ‘ed’. QED uses RE for searching text. RE became useful in the Unix text processing program ‘grep’ and modern programming languages such as ‘PERL’. A Canadian computer scientist Henry Spencer wrote ‘regex’, which is widely used as a software library for RE.

They are called ‘regular’ because they describe a language with very ‘regular’ properties. ...