January 27th, 2012
Any language L that accepts a regular expression r is regular.
GNFA - General Nondeterministic Finite Expression
A GNFA N accepts a string w, if there is a walk from the start-state of N to a
▯nal state of N, that is labeled with a regular expression r, usch that w 2 L(r).
Example: Insert image from Regular Languag▯s notes ▯3.12).
The above GNFA accep