Find the count of all Brzozowski's derivatives of a given language

27 Views Asked by At

Given the language L = {$a^nb^n: n\in \mathbb{N}$} I have to find the number of derivatives I can produce from it. I wrote down some of them and I feel like the number of them must be infinite, is that correct? For every n there will be for example $(a^n)^{-1} L$, but also ($a^{n-1})^{-1} L$ etc... Can someone tell me if my reasoning is right?

1

There are 1 best solutions below

0
On BEST ANSWER

You’re right, but you can make it much clearer by actually identifying the derivatives: for each $n\in\Bbb N$

$$(a^n)^{-1}L=\{a^kb^{k+n}:k\in\Bbb N\}\,,$$

and these are clearly all distinct languages.