Post Closed as "duplicate" by David Richerby, Yuval Filmus, fade2black, Evil, Kyle Jones of
2 edited title

1

# Decide whether the Language is regular

how would you prove if this language is regular/irregular?

question given:

Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, give a formal proof(based on the Pumping Lemma).

i) {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0 are three integers};

I have constructed a DFA which I believe proves the language is regular however, using the pumping lemma i.e. where the pumping length (p) = 4: aaaabbbbcccc, and say this is split into xyz where x = aa, y = aa and z = bbbbcccc then x(y^i)z where i = 2 -> aaaaaabbbbcccc

satisfy the conditions of the pumping lemma:

1. for each i >= 0, x(y^i)z ∈ A
2. |y| > 0
3. |xy| <= p

so:

1. when i = 2, x = aa, y = aa, z = bbbbcccc then A = aa aaaa bbbbcccc is satisfied
2. |y| = aa so |y| = 2 which satisfies the condition
3. x = aa + y = aa so |xy| = 4 which satisfies the condition

meaning the language is regular BUT if:

x = aaa, y = ab, z = bbbcccc

1. when i = 2, x = aaa, y = ab, z = bbbccc then A = aaa abab bbbccc which doesn't satisfy the condition as they're not in order (a then b then c) anymore.

2. |y| = ab so |y| = 2 which satisfies the condition.

3. x = aaa + y = ab so |xy| = 5 which doesn't satisfy the condition.

I could be using the Pumping Lemma completely wrong I'm confused as initially (and from my DFA) I assumed this language is regular as the number of a's doesn't depend on the number of b's and the number of c's doesn't depend on the number of b's or a's etc.

basically: I think I have proven that the language is regular with a DFA but irregular with the pumping lemma and don't know how to give a definitive answer.