Regular Languages Among Given Options: A Formal Language Analysis

We are asked which of the following languages is regular. Recall that a language is regular if it is recognized by some DFA/NFA (equivalently, if it satisfies the structural constraints of finite automata). For non-regularity, we typically use the pumping lemma for regular languages, which says every regular language must have a “pumping length” that can be exploited to generate new strings that still stay in the language.

We assume the input alphabet includes at least one symbol (typically $\Sigma=\{0,1\}$ in these problems).

Footnotes

1. Properties of Regular Languages - Notes on regular languages and closure concepts. ↩

2. Pumping lemma for regular languages - Statement of pumping lemma used for non-regularity proofs. ↩

Quick answer

• (i) Not regular: length is a prime number.
• (ii) Not regular: palindromes.
• (iii) Not regular (in general): strings containing substring $ww^r$ (depends on the factorization; the required equality-of-unbounded halves gives non-regularity).
• (iv) Regular: strings with an even number of $0$’s.

We now justify each item rigorously.

(i) Strings whose length is a sequence of prime numbers

Key idea

Let $\Sigma=\{0\}$ for a moment and consider the unary language

$$L_{\text{prime}}=\{0^p \mid p \text{ is prime}\}.$$

If the original language “strings whose lengths are prime” were regular, then this unary subset would also be regular (by standard reasoning using intersection with a regular set; regular languages are closed under intersection).

But the unary language of prime lengths is a known non-regular language; one can prove it via the pumping lemma for regular languages.2

Pumping-lemma sketch (why prime lengths fail)

Assume $L_{\text{prime}}$ is regular. Let $p$ be its pumping length. Choose a prime $\ell>p$ and consider the string $0^\ell\in L_{\text{prime}}$. The pumping lemma guarantees a decomposition $0^\ell=xyz$ where $|xy|\le p$ and $|y|\ge 1$ such that for all $i\ge 0$, the pumped string $xy^iz$ is still in the language.

However, pumping changes the length away from $\ell$ (by adding/removing copies of $y$), producing $0^{\ell'}$ where $\ell'$ is not prime for some $i$—contradiction.2

So option (i) is not regular.

Keywords: pumping lemma unary language pumping length closure under intersection

Footnotes

1. Proof: The language consisting of strings whose lengths are prime is not regular - Pumping-lemma style proof for prime-length unary language. ↩ ↩²

2. Pumping lemma for regular languages - Statement of pumping lemma used for non-regularity proofs. ↩ ↩² ↩³

(ii) Palindrome strings

Key idea

Let

$$PAL=\{w\in\Sigma^* \mid w=w^R\}.$$

The palindrome condition requires the automaton to “match” the first half with the second half in reverse order, which cannot be done with finite memory for unbounded lengths.

A standard pumping lemma proof picks a long palindrome $w$ with a large enough “middle” that any allowed pumping changes one side but not the corresponding mirrored side, so the result is no longer a palindrome.2

For example, in many pumping-lemma constructions one chooses $w=0^n 1 1 0^n$ (or similar) and pumps within the prefix region; the pumped string preserves the pumped prefix length but breaks equality with the suffix, contradicting membership in $PAL$.2

Thus option (ii) is not regular.

Keywords: palindrome language mirror constraint pumping-lemma proof finite automaton

Footnotes

1. 4 Showing that a language is not regular - Pumping lemma example for palindromes. ↩ ↩²

2. Pumping lemma for regular languages - Statement of pumping lemma used for non-regularity proofs. ↩ ↩²

(iii) Strings containing substring $ww^r$

Interpret the option as the set

$$L_{ww^r}=\{x\in\Sigma^*\mid \exists w \text{ such that } ww^R \text{ occurs as a substring of } x\}.$$

Key idea

The substring requirement contains an exact reversal match between two unbounded parts. Even though it is “local” (a substring), the existence of some $w$ still requires equality between a segment and its reverse. This “self-similarity under reversal” generally prevents regularity.

A common proof strategy for such languages is to assume regularity and then apply the pumping lemma: pumping a part of a long witness string either breaks the required equality structure inside the occurrence of $ww^R$ or yields strings where no such $ww^R$ occurrence can be formed. Discussions and example analyses for languages built from $ww^R$-type patterns are typically handled via pumping lemma style contradictions.2

Therefore, option (iii) is not regular (in general).

Note: If the problem were restricted to a fixed size of $w$, it would become regular. But with unbounded $|w|$, the reversal-equality constraint is the obstacle.

Keywords: substring reversal factor $ww^R regularity obstruction

Footnotes

1. Regular Languages; Pumping Lemma (and $ww^R$-type discussion) - Notes illustrating pumping lemma usage for languages involving reversal/equality constraints. ↩

2. Pumping lemma for regular languages - Statement of pumping lemma used for non-regularity proofs. ↩

(iv) Strings with even number of $0$’s

Key idea

This is a classic DFA-recognizable property: count parity of $0$’s.

Let

$$L_{\text{even}}=\{x\in\{0,1\}^*\mid \#0(x)\text{ is even}\}.$$

A DFA with two states suffices:

• state $q_E$ meaning “seen an even number of $0$’s so far”
• state $q_O$ meaning “seen an odd number of $0$’s so far”

On reading:

• a $0$: toggle between $q_E$ and $q_O$
• a $1$: stay in the same state

This construction is standard and makes $L_{\text{even}}$ regular.

So option (iv) is regular.

Keywords: DFA construction parity automaton toggle transition regular language

Footnotes

1. DFA machines accepting odd number of 0's or even number of 1's (parity DFA) - Example construction for parity of symbol counts. ↩

Final classification

Footnotes

1. Proof: The language consisting of strings whose lengths are prime is not regular - Pumping-lemma style proof for prime-length unary language. ↩

2. Pumping lemma for regular languages - Statement of pumping lemma used for non-regularity proofs. ↩ ↩² ↩³

3. 4 Showing that a language is not regular - Pumping lemma example for palindromes. ↩

4. Regular Languages; Pumping Lemma (and $ww^R$-type discussion) - Notes illustrating pumping lemma usage for languages involving reversal/equality constraints. ↩

5. DFA machines accepting odd number of 0's or even number of 1's (parity DFA) - Example construction for parity of symbol counts. ↩