1
$\begingroup$

I have the following language: $L=\{a^{j}b^{k}\,:\,j,k\geq0\}$. I'm trying to prove that it is a regular language. I can use the following theorem:

Let $r$ be a regular expression then $L[r]$ is regular language.

So I can use $r=a^*b^*$ to be that regular expression and then $L[r]$ is regular. But I think that I'm missing something. What explanation should I give for using that exactly $r$. In other words, how a formal proof should look like? I'm taking automata and formal languages this semester and I need to be as formal as possible. Could you please should how should I prove it "formally"?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I don't think you need any clarification, but if you insist, you could write $$ L = \{a^{j}b^{k} \mid j,k \geqslant 0\} = \{a^{j} \mid j \geqslant 0\}\{b^{k} \mid k \geqslant 0\} = a^*b^*. $$

$\endgroup$
2
  • $\begingroup$ But why? What if the language is more complicated. For example, find a regular expression that represents all the words over $\Sigma=\{a,b\}$ where there are no $aa$. I would say $r=(b^*(ab)b^*)^*(a+\epsilon)+a+b^*$. But does it really satisfies the requirements? $\endgroup$
    – vesii
    Feb 12, 2020 at 21:53
  • $\begingroup$ The situation is completely different here. I just show that your language is the product of two simpler languages. It just relies on the definition of the concatenation product and the definition of the star operation. No regular expressions are needed. $\endgroup$
    – J.-E. Pin
    Feb 12, 2020 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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