patternMinor
Check the Regularity of the folowing Languages
Viewed 0 times
regularitythechecklanguagesfolowing
Problem
Let $A$ be a regular set. Consider the two sets below.
\begin{align*}
L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\
L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}.
\end{align*}
Which of the following is true?
What I knew
$Y \in A $ only but now the relation between $y$ and $x$ is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.
Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.
With this understanding I came to a conclusion that $L_1$ is regular.
But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.
\begin{align*}
L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\
L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}.
\end{align*}
Which of the following is true?
- $L_1$ and $L_2$ are regular
- $L_1$ is regular but $L_2$ is not
- $L_2$ is regular but $L_1$ is not
- Both are not regular
What I knew
$Y \in A $ only but now the relation between $y$ and $x$ is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.
Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.
With this understanding I came to a conclusion that $L_1$ is regular.
But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.
Solution
Your reasoning regarding $L_1$ is wrong. What you show is that for each $n$, the following language is regular whenever $A$ is regular:
$$
L_1^{(n)} = \{ x : x^n \in A \}.
$$
The language $L_1$ is the infinite union of $L_1^{(n)}$ for all $n \geq 0$. Unfortunately, regular languages are not closed under infinite union (for example, every unary language is an infinite union of singleton languages).
Nevertheless, $L_1$ is regular. Given a DFA $\langle Q,q_0,F,\delta \rangle$ for $A$, we construct a DFA for $L_1$ whose set of states is the set of all functions $Q \to Q$. The initial state $id$ is the identity function, and we construction the automaton so that $\delta_{L_1}(id,w)$ is the function that maps $\sigma \in Q$ to $\delta(\sigma,w)$. This gives us enough information to determine whether any power of $w$ belongs to $A$.
The language $L_2$, in contrast, is not necessarily regular. For example, if $A = ab^$ then $L_2 \cap ab^ab^* = \{ ab^n ab^n : n \geq 0 \}$, which isn't regular.
$$
L_1^{(n)} = \{ x : x^n \in A \}.
$$
The language $L_1$ is the infinite union of $L_1^{(n)}$ for all $n \geq 0$. Unfortunately, regular languages are not closed under infinite union (for example, every unary language is an infinite union of singleton languages).
Nevertheless, $L_1$ is regular. Given a DFA $\langle Q,q_0,F,\delta \rangle$ for $A$, we construct a DFA for $L_1$ whose set of states is the set of all functions $Q \to Q$. The initial state $id$ is the identity function, and we construction the automaton so that $\delta_{L_1}(id,w)$ is the function that maps $\sigma \in Q$ to $\delta(\sigma,w)$. This gives us enough information to determine whether any power of $w$ belongs to $A$.
The language $L_2$, in contrast, is not necessarily regular. For example, if $A = ab^$ then $L_2 \cap ab^ab^* = \{ ab^n ab^n : n \geq 0 \}$, which isn't regular.
Context
StackExchange Computer Science Q#65176, answer score: 7
Revisions (0)
No revisions yet.