0
$\begingroup$

given this information of a language I need to determine if the language is regular or not: enter image description here

I thought to Assume by way of contradiction that L6 satisfies the conditions of the pumping lemma. Let p be the pumping constant. Consider the word w = 0^(P-1)1... Clearly w ∈ L6. Thus, by the pumping lemma, there exist x, y, z ∈ Σ^* such that w = xyz, |xy| ≤ p, |y| > 0 where: x = 0^m,
y =0^(p-1-m)1,z = etc, the part that left of t he word. if we take i = 1000 for example we get that xy^1000z not in L because we get the following expression: 000000(00000...001)^1000...z (not in L6), but the solution that provided to similar question shows this: enter image description here

where am I wrong in my attitude to the question?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The language is regular because of the restriction $i_2 < 99$ which makes everything finite. Once you have 99 initial zeroes, it doesn't matter how many more you have. So the pumping lemma isn't going to help. There are a few ten thousand states. Try figuring out what they are.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, for your fast answer. I see the regular expression and the 10K possibilities, I think I had problem in making assumption as to what thee partition of the word w into xyz looks like, instead of considering all possible options of partition. $\endgroup$
    – user1701057
    Apr 9 at 17:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.