# How to describe the languages of these regular expressions in plain English?

This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck.

The question is

Give English description of the languages of the following regular expressions.

1. $$(1+\epsilon)(00^*1)^*0^*$$
2. $$(a^*b^*)^*aaa(a+b)^*$$
3. $$(a+ba)^*b^*$$

I could only guess that the second one as the set of strings that at least have three consecutive $$a$$s. But I'm really clueless about others. Can someone make this clarified for me? Any help is highly appreciated.

The first regular expression captures all strings over $$\{0,1\}$$ not containing two consecutive 1s. It is not hard to check that any string in the language of the given regular expression has this property, and with some more work you can show the converse.
The second regular expression captures all strings over $$\{a,b\}$$ containing $$aaa$$ as a (consecutive) substring, as you also noticed.
The third regular expression captures all strings over $$\{a,b\}$$ not containing $$bba$$ as a (consecutive) substring, though this perhaps requires some verification.
• Certainly not. Its language contains $bb$, for example. Mar 12, 2020 at 15:27