0
$\begingroup$

I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ defines the language $L(r) = a^{*} $. I am looking for any kind of tip, I think I can use a pumping lemma somehow, but I am not sure how exactly.

$\endgroup$
3
  • $\begingroup$ If r is a regular expression then you know that L(r) is regular. The pumping lemma isn't going to help you. $\endgroup$ – gnasher729 Jan 10 at 12:50
  • $\begingroup$ Tip 1: Create a finite state machine for that language from the regular expression. Every state must be a final state. $\endgroup$ – gnasher729 Jan 10 at 12:54
  • $\begingroup$ Tip 2: Call a set S of integers a "regular set" if it is finite, or of the form { ak + b: k ≥ 0 } for some a > 0, b ≥ 0 }, or the union of a finite number of regular sets. Show that for every regular expression, the language is { a^k: k is in some regular set }. Figure out how to calculate these regular sets. L(r) = a* if the regular set is { al + b: k ≥ 0 } with a = 1 and b = 0. $\endgroup$ – gnasher729 Jan 10 at 12:58