1.3 regular expressions
Properties of Regular Language
Unions, intersections, differences and complements of regular languages are regular.
Formal Def of a Regular Expression
Say that R is a regular expression if R is: - for some in the alphabet - - - () - () - ()
() are regualr expressions(inductive def)
- L(R): the language of R
- concatenating the empty set to any set yields the empty set, so
Equivalence with Finite Automata
- hint: regular language is one that is recognized by some finite automation
- a language is regular iff some regular expression describes it
- prove see textbook p67 p70
- GNFA: generalized nondeterministic finite automation, its transition arrows may have any regular expression as labels
DFA to regular expression
Write a table out.
Row: all combination of two states
Base Case: when k=0, if there is a transition(including this state and itself, in this case is ), then is the combination(or+transitions if more than one); if there is not, then it is empty.
Then fill the table using formula.
The result should be
Suppose it is regular. Let p be its pumping constant.
Consider the string w=xxx, which is a string in this language with length greater than p.
There must be a pumping decomposition of w: w=xyz, where and .
Prove this compositions variants is not in the language.
Then this violates the pumping lemma.
So it is not regular.