Automata: Trying to understand how to check if language is regular

[milena24]

Homework Statement

Prove or Disprove L is regular, where
L = {0[tex]^{i}[/tex]1[tex]^{j}[/tex] | (i[tex]^{2}[/tex] + j[tex]^{2}[/tex]) is square}

Homework Equations

N/A

The Attempt at a Solution

I tried using pumping lemma, but I don't know how to assign p if there are two variables (i and j)...

I understand the i[tex]^{2}[/tex] + j[tex]^{2}[/tex] would be like pythagorean theorem, but I cannot relate the pumping lemma given I've been provided two distinct variables...

Can anyone help and guide me? I am not asking for a full solution, instead a bit of a kickstart

 

[KataKoniK]

.

First, let's simplify the language L by considering only the values of i and j that are non-negative integers. This means that i and j can only take on values of 0 or greater.

Now, let's assume that L is regular. This means that there exists a deterministic finite automaton (DFA) that recognizes L.

Let's call this DFA M. M has a finite number of states, let's say n. This means that if we input a string of length n or greater into M, there must be a repeated state in the computation. This is the basis of the pumping lemma.

Now, let's consider the string 0^{n}1^{n}. This string is in L because (n^{2} + n^{2}) = 2n^{2} is a perfect square (specifically, 2n^{2} = (n\sqrt{2})^{2}).

If we input this string into M, there must be a repeated state in the computation. This means that there exists a substring of the form 0^{p}1^{q} such that pumping this substring will still result in a string that is in L.

Let's pump this substring by repeating it k times, where k is a positive integer. This results in the string 0^{p+k}1^{q+k}.

Now, let's consider the value of (p+k)^{2} + (q+k)^{2}. This can be expanded to p^{2} + 2pk + k^{2} + q^{2} + 2qk + k^{2} = (p^{2} + q^{2} + 2k(p+q) + 2k^{2}).

Since p and q are fixed values, (p^{2} + q^{2}) is a perfect square. Additionally, 2k(p+q) is also a perfect square because it is a multiple of 2. This means that (p^{2} + q^{2} + 2k(p+q) + 2k^{2}) is also a perfect square. Therefore, 0^{p+k}1^{q+k} is still in L.

However, this is a contradiction because we know that (p+k)^{2} + (q+k)^{2} is not a perfect square for all values of k (