patternMinor
Why is this language a regular language?
Viewed 0 times
thiswhyregularlanguage
Problem
Came across this in a book, and I'm wondering why the following language is regular?
$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$
Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a regular language because it can be expressed by a regular expression $$a*$$, and $$ \{ww^R: w \in \{a,b\}^3\} $$ is a regular language because it is finite; therefore the union of the two regular languages makes a regular language?
$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$
Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a regular language because it can be expressed by a regular expression $$a*$$, and $$ \{ww^R: w \in \{a,b\}^3\} $$ is a regular language because it is finite; therefore the union of the two regular languages makes a regular language?
Solution
This is not an union of two regular languages! It's a concatenation. Note the difference,
That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by constructing two NFAs for the regular languages and connecting the accepting states of $L_1$ to the starting states of $L_2$ by an $\epsilon$-transition.
- Union: $L_1 \cup L_2$
- Concatenation: $\{ab : a \in L_1 \wedge b \in L_2\}$.
That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by constructing two NFAs for the regular languages and connecting the accepting states of $L_1$ to the starting states of $L_2$ by an $\epsilon$-transition.
Context
StackExchange Computer Science Q#126488, answer score: 6
Revisions (0)
No revisions yet.