3.2 CONNECTION BETWEEN REGULAR EXPRESSIONS AND REGULAR LANGUAGES
As the terminology suggests, the connection between regular languages and regular expressions is a close one. The two concepts are essentially the same; for every regular language there is a regular expression, and for every regular expression there is a regular language. We will show this in two parts.
Regular Expressions Denote Regular Languages
We first show that if r is a regular expression, then L(r) is a regular language. Our definition says that a language is regular if it is accepted by some dfa. Because of the equivalence of nfa’s and dfa’s, a language is also regular if it is accepted by some nfa. We now show that if we have any regular expression r, we can construct ...
Get An Introduction to Formal Languages and Automata, 7th Edition 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.
