Connection between regular expressions and regular languages

Regular Expressions and Regular Languages
for every regular language there is a regular expression
for every regular expression there is a regular language.

Regular Expressions and Regular Languages
Regular Expressions denote Regular Languages

Regular Expressions and Regular Languages

Regular Expressions and Regular Languages

Regular Expressions and Regular Languages

Exercise

Regular Expressions for Regular Languages
for every regular language, there should exist a corresponding regular expression.
For every regular language there should be an NFA that accepts it.
From the NFA, we can extract the respective regular expression using generalized transition graphs (GTG)
From construct the equivalent Generalized Transition Graph in which transition labels are regular expressions.

Example

Reducing the states
Reducing the states

Example (cont.)
Resulting Regular Expression:

In General
Removing states:

In General
The final transition graph:
The resulting regular expression: