1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Is it correct to say that the last regex captures strings that have no consecutive b's? $\endgroup$
    – Pavindu
    Mar 12, 2020 at 15:26
  • $\begingroup$ Certainly not. Its language contains $bb$, for example. $\endgroup$ Mar 12, 2020 at 15:27
  • $\begingroup$ I don't think so. (a+ba)*b* means zero or more times of a OR zero or more times of ba, followed by zero or more times of b. Then bb will not be an accepted string for this regex. Please correct me if I'm wrong. $\endgroup$
    – Pavindu
    Mar 12, 2020 at 15:34
  • 1
    $\begingroup$ We’ll have to part in disagreement. $\endgroup$ Mar 12, 2020 at 15:35
  • $\begingroup$ Oh after a year I see my mistake there. It does contain bb, because of b*🙃 $\endgroup$
    – Pavindu
    Feb 14, 2021 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.