Need help w/automata theory

[solnushka]

Can anyone help me prove that this language is not regular:

set consisting of binary strings x such that x is prime OR even.

?:sad:

[NetAnderthal]

oh shait, homework is due when? :)
Read up on Pumping Lemma (http://www.cs.rpi.edu/~goldberg/NOTES-aut/node6.html)

Pumping lemma: Let be a deterministic finite automaton and let L be a language accepted by M.
If w belongs to L(M) and |w| =>|Q|, then w can be split into three parts, w = x y z, such that

1. |xy| <= |Q|;
2. |y| >0; and
3. for all integers n >=0 , string x(y^n)z belongs to L .


if any of these 3 conditions are not met -> the language is non-regular. I suggest using proof by contradiction



Btw, I dont think you can build a DFA for prime numbers -- so that could be a step in the direction of the proof


But hey, look at pages 5 & 6 here (http://www-cse.stanford.edu/classes/cs150/handouts/15.pdf) for proof examples

[solnushka]

Spasibo :)

Na samom dele ya dokazala ispol'zuya set theory: A union B is A+B-(A intersect B)
Pumping lemma ne dokazivaet: y tebia 2 sets: prime is not regular and evens is regular. You need to prove that the union of them is not regular.

A test vse ravno zavalila :(