0
$\begingroup$

Over the alphabet $\Sigma=\{0,\ldots,9,/\}$, is the following language regular:

$$L=\left\{x/y/z:z=\mathrm{str}\bigl(\mathrm{int}(x)+\mathrm{int}(y)\bigr)\right\}$$

where $\mathrm{str}$ maps an integer to its decimal representation, and $\mathrm{int}$ does the opposite thing.

It contains $0/0/0$, $10/34/44$, $1/999/1000$ and so on. It is not an homework or something, I am just curious.

$\endgroup$

1 Answer 1

1
$\begingroup$

It is not regular. Consider the strings "$1^n/0/$" which must be followed by exactly n 1's. So with a finite state machine, after processing $1^n/0/$, we must be in a state $S_n$ which ends up in an accepting state if and only if we process exactly n further 1's. So for n ≠ n', the states $S_n$ and $S_{n'}$ are different, which means the finite state machine has an infinite number of states.

$\endgroup$
1
  • $\begingroup$ Thats a nice proof thank you $\endgroup$
    – user160778
    May 25, 2023 at 22:27

Your Answer

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