Compilers: Principles and Practice by Pearson

Formal Languages and Automata 425

Consider string ‘0010’ ∈ L

3

. Here, we can take u = 0, v = 0, w = 10 and see that PL is satisfied.

You can try with other strings accepted by the FSM and confirm that L

3

is indeed regular. In fact, the

very fact that we are able to give an FSM for it shows that it is regular.

A.4.6 Implementation Notes

REs are used extensively in computer science and engineering at several levels and places. Apart from

its use in design of language compiler, assemblers, etc. they are also used in:

c

Command language of Unix/Linux like languages;

c

In utilities like grep, sed, awk;

c

In text editors, pagers like less;

c

Perl has extensive ...