1
$\begingroup$

I need to know if this language $$ L = \{ \ (a^2b^2c^2)^n \mid n > 0\ \} $$ is regular or not.

Since it is trivial to design an FSA with a loop that accepts that language, it is regular. For example here is my FSA that accept language L using draw.io

https://i.stack.imgur.com/UfgZb.png

I'm trying to prove that it is regular by using the pumping lemma.

My try:

Suppose $L$ is regular.

I choose $3$ as pumping length $P$

$$ |S| \geqq P $$

Using my string $S = aabbcc\ aabbcc\ aabbcc$

The first block is $x$, the second is $y$ and the third is $z.$

I pump $y$ in $yy$ and I got

$aabbcc\ aabbcc\ aabbcc\ aabbcc$

And this satisfies the first condition because $ xy^iz \in L $ The second is satisfied also because $ |y|>0.$

But I need some help for the third condition that is

$$ |xy|\leq P $$

$|xy|$ is the length of the first string or the second, where I applied the pumping lemma? How can I calculate this?

Since $P$ is $3$ (because it is chosen by me) I can't verify this language.

Any help appreciated. Thank you.

$\endgroup$
1
$\begingroup$

As a preliminary observation, your automaton assumes that the alphabet is $\{aa,bb,cc\}$. If the alphabet is $\{a,b,c\}$ instead, you need seven states.

With the preliminary out of the way, the pumping lemma for regular languages is typically used to prove that a language is not regular (as noted by @ChistianIvicevic). All you can do if the language is regular is to verify that it satisfies the conditions spelled out in the lemma. Let's see why you are having difficulty doing that.

The lemma says that for a regular language $L$ there exists a constant $P$, which is known as the pumping length, such that some condition that depends on $P$ is true.

This means that in verifying that the pumping lemma holds for $L$, you don't get to pick an arbitrary $P$: you have to find a value that works. If you have an automaton for $L$ with $n$ states, it's easy: $P$ should be at least $n$. (Why? Because the pumping lemma rests on a simple application of the pigeonholing principle: if there are more letters in an accepted word than states in the automaton, at least one state will be visited twice when the automaton reads the word.)

Assuming your automaton has four states (that is, $aa$ is a single letter) $P=3$ is not a good choice. With $P=4$ you can still choose the same $S$ as you did, though $S' = aabbcc~aabbcc$ is enough for demonstration purposes.

Now you can split $S'$ into $x=\epsilon$, $y=aabbcc$, and $z=aabbcc$ and verify that all conditions are met.

Alternatively, you can split $S$ into $x=\epsilon$, $y=aabbcc$, and $z=aabbcc~aabbcc$ and verify that all conditions are met.

The lemma says that there exists $P$ (you have to pick a good one) such that for any $S$ in $L$ of length at least $P$ (here you get to choose freely among the words in the language that are long enough) there is a way to write $S$ as $xyz$ (once again, you have to split correctly, not arbitrarily) such that all conditions are met.

In your example, you chose $P$ and the way to split $S$ arbitrarily. Therefore the fact that not all the conditions on $x,y,z$ were satisfied does not contradict the pumping lemma.

If you have an automaton for $L$, as you do, not only picking $P$, but also splitting a word in $L$ is easy: just run it through the automaton and find the first state visited more than once. Then $x$ is the prefix of the word that takes the automaton to that state the first time, $y$ is the segment of the word that causes the automaton to loop back to that state, and $z$ is the rest of the word.

$\endgroup$
1
$\begingroup$

Your language is $(aabbcc)^+$ (= $aabbcc(aabbcc)^*$ if you prefer). Since it is given by a regular expression, it is regular. No need of computing an automaton for that.

$\endgroup$
0
$\begingroup$

The pumping lemma states that all regular languages satisfy certain conditions but the converse it not true. A language that satisfies mentioned conditions may still be non-regular. Thus the pumping lemma is a necessary but not sufficient condition.

To prove a language is regular you can either:

  1. Construct an NFA that accepts the language.
  2. Construct a regular expression that describes all words from the language.
  3. Construct a regular grammar that matches the language.

You just have to show correctness in each variant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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