snippetModerate
How to prove regular languages are closed under left quotient?
Viewed 0 times
leftlanguagesareregularclosedproveunderquotienthow
Problem
$L$ is a regular language over the alphabet $\Sigma = \{a,b\}$. The left quotient of $L$ regarding $w \in \Sigma^*$ is the language
$$w^{-1} L := \{v \mid wv \in L\}$$
How can I prove that $w^{-1}L$ is regular?
$$w^{-1} L := \{v \mid wv \in L\}$$
How can I prove that $w^{-1}L$ is regular?
Solution
Assume $M$ is a deterministic finite state machine accepting $L$. Feed the word $w$ into $M$, which will land you in some state $q$. Construct a new machine $M'$ which is the same as $M$ but has start state $q$. I claim that $M'$ accepts $w^{-1}L$.
Now prove it.
Now prove it.
Context
StackExchange Computer Science Q#1326, answer score: 16
Revisions (0)
No revisions yet.