Consider the languages Σ = {a, b} and Γ = { Ø, λ, ∪, (, ), a, b }. Let L ⊆ Σ such that for all x ∈ L, x is a regular expression for Σ.
Is the language Γ regular?
Name:
Anonymous2009-02-06 16:44
Regular expression require an equal number of left and right parentheses, which cannot be expressed by a finite state acceptor. In fact, any programming languages using parentheses, such as lisp, are not regular.