formally specify language defined by the following regular expressions?

Question

I am studying for an exam in the morning using a past exam provided by the professor without solutions. Unfortunately I missed the day the exam was solved in class and therefore can't figure out how to do this set. I have spent the past hour searching google for a clear explanation and can't seem to understand. I will list the problem exactly. My main questions are what makes a language definition formal, and why aren't the expressions listed already considered the language? I hope this makes sense, I have been up for way too many hours looking at this.

Formally specify the languages defined by the following regular expressions. If you provide regular expressions, please be sure to reduce them to their simplest forms.

(a) (11|111)*

(b) (ε|φ*1|0φ)+

(c) (0|1)|1

If you could help with any of these and explain the process I can do the rest. Thank a lot.

Formally specify the languages defined by the following regular expressions. If you provide regular expressions, please be sure to reduce them to their simplest forms.

(a) (11|111)*

(b) (ε|φ*1|0φ)+

(c) (0|1)|1

If you could help with any of these and explain the process I can do the rest. Thank a lot.

t · Accepted Answer

I am also unsure what makes a language definition formal, but I do know that all three regular expressions can be simplified:

(a) ε|111*
(b) (φ*1|0φ)*
(c) 0|1

Explanations:
(a) Two or three 1's, repeated any number of times, can be used to make the empty string (ε) and any string with two or more 1's. Note that the closure (*) applies only to the last 1, so the regular expression I gave is equivalent to ε|11(1*).
(b) I assumed ε is the empty string and φ is a normal symbol. The only difference made by the ε is that it allows the empty string -- using ε otherwise makes no difference. Closure (*) is the same as + except that it also allows the empty string, so it can be used to eliminate ε.
(c) The second 1 is redundant.

Good luck in the exam.

Trending News

formally specify language defined by the following regular expressions?

1 Answer