HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

How to prove regular languages are closed under left quotient?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#1326, answer score: 16

Revisions (0)

No revisions yet.