- There exists a DFA that specifies
- There exists an NFA without -transitions that specifies
- There exists an NFA with -transitions that specifies
- There exists a Regular Expression that specifies
What are examples of language that is not regular?
- The language of words of balanced parentheses is an example of a context-free but nonregular language.
- The language of words with arithmetic expressions with parentheses.
- The language of words with an equal number of occurrences of a and b is yet another example.
Generally, any language that allows for “nesting” will not be regular -> So any language that is ambiguous?