1
$\begingroup$

I am analyzing the regularity of the following two languages defined over the alphabet $\Sigma = \{a, b\}$:$$L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ \text{ AND } \beta \in \{a, b\}^+ \}$$$$L_2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+ \text{ AND } \beta \in \{a, b\}^+ \}$$The question asks which of the following statements is CORRECT:

(A) Both L1​ and L2​ are regular languages.

(B) L1​ is a regular language but L2​ is not a regular language.

(C) L1​ is not a regular language but L2​ is a regular language.

(D) Neither L1​ nor L2​ is a regular language.


My Analysis and Confusion:

My understanding is that both languages require a comparison of an arbitrary-length prefix with an identical suffix, separated by a non-empty string, which typically makes a language non-regular as it requires infinite memory.
For $L1$​ and $L2$​: I considered the intersection of both languages with the regular language $R=a∗ba∗$.$$L_1 \cap R = L_2 \cap R = \{ a^k b a^k \mid k \ge 1 \}$$Since $a^k b a^k$ (for $k \ge 1$) is a standard example of a non-regular language (proven using the Pumping Lemma), and the intersection of a regular language with $L$ is regular if $L$ is regular, this strongly suggests that both $L_1$ and $L_2$ are non-regular. Based on this, my derived answer is (D).

The Official Answer:

The official provided answer for this question is (C), which claims that:$L_1$ is not a regular language. (This aligns with my analysis). $L_2$ is a regular language. (This contradicts my analysis). I am seeking clarification. Is my analysis of $L_2$ being non-regular incorrect? If $L_2$ is indeed regular, how can it be proven? I suspect there might be a simpler equivalent definition of $L_2$ that I am overlooking, or a flaw in using the intersection method for $L_2$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

$L_2$ is indeed regular. In fact, $L_2 = a\Sigma^+a$, with $\Sigma= \{a,b\}$:

  • Let $u\in a\Sigma^+a$, $u = ava$, with $v\in \Sigma^+$. Then, with $\alpha = a$ and $\beta = v$, $u = \alpha \beta\alpha\in L_2$.

  • Conversely, let $u \in L_2$, $u = \alpha \beta \alpha$, with $\alpha \in \{a\}^+$, $\beta \in \Sigma^+$. Since $\alpha \in \{a\}^+$, $\alpha = a^k$ for some $k\geqslant 1$.

    Then, define $v = a^{k-1}\beta a^{k-1}\in \Sigma^+$. We have $u = ava\in a\Sigma^+a$.

Your mistake was the (wrong) equality $L_2\cap R = \{a^kba^k\mid k\geqslant 1\}$. Indeed, for example, $aaba\in L_2\cap R$, since $aaba\in R$ and $aaba = \alpha \beta \alpha$ for $\alpha = a$ and $\beta = ab$.

Also note that since $L_2\subset L_1$, your intersection $L_1\cap R$ is also wrong.

Improve this answer
$\endgroup$
1
$\begingroup$

$L_2$ is regular because it starts and ends with same symbol $a$, and regular expression for $L_2$ is $a(a+b)^+a.$

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.