Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 24, 2010 #1
    1. The problem statement, all variables and given/known data
    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}


    2. Relevant equations
    N/A


    3. 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
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?