Automata Theory Question

[nikonratm]

Hey can someone help me with this question, it's killing me!

---------------------------------
Determine whether the following language is regular or not, and prove your answer:

{x such that there exists a non-empty z such that x contains zzz as a substring}

You may assume that there are arbitrarily long strings in the complement of this language—that is, there are arbitrarily long strings that do not contain a non-empty substring of the form zzz.
---------------------------------

thanks so much

[cipher1024]

it is regular.u can also draw a dfa for that language.

[mehdi62b]

Alphabet={a,b,c,...}
z=(a+b+c+...)+
z represents a regular language so its concatenations(Z^3) would also represent a regular language.
(a+b+c+...)*Z^3(a+b+c+...)* is a regular expression.

[RoboTact]

Hei!
Don't confuse things.
It's said 'z is not empty', so z is a word, not just letter. For this case language is NOT regular. DFA need to 'remember' first occurance of word to match it with second and third, which it can't, as it's finite but words aren't.

[RoboTact]

Alphabet={a,b,c,...}
z=(a+b+c+...)+
z represents a regular language so its concatenations(Z^3) would also represent a regular language.
(a+b+c+...)*Z^3(a+b+c+...)* is a regular expression.'abc' as accepted by your language.
it is regular.u can also draw a dfa for that language.Can you do it?

[nikonratm]

i think i agree that it is not regular but part two is more confusing to me, it reads:

----------------
suppose the opposite assumption, that there is a bound n on the length of strings in the alphabet not containing a nonempty substring of the form zzz. What is the answer now? Prove it.
----------------

my intuition is that this new language is regular, if we chose n to be the number from the pumping lemma. but that number only works one way, i.e. if a string is that long it contains one of the symbols more than once...it does not say that strings shorter than n do not contain repetitions of a symbol...so im not sure???

[RoboTact]

It doesn't matter. The fact is that there is just finite set of words (zzz for z of length equal or no more then n - in any case), and language is set of words containing as substring any word from that set. For such language NFA is obviously constructed.

[nikonratm]

It doesn't matter. The fact is that there is just finite set of words (zzz for z of length equal or no more then n - in any case), and language is set of words containing as substring any word from that set. For such language NFA is obviously constructed.

sorry, im not sure what you mean, can you explain a bit further?
thanks