Closure under splitting?

18 Views Asked by At

Say there is a regular language $L\subseteq \lbrace 0,1\rbrace^\ast$

Would the language $L_1 =\lbrace w\in\lbrace 0,1\rbrace^\ast | w0\in L\rbrace $ also be regular? (i.e. $L = L_1\circ\lbrace 0\rbrace$)

I know that given

$L = L_1 \circ L_2$,

if $L_1$ and $L_2$ are regular, so is $L$, however I'm not sure that if that $L$ and $L_2$ are regular, $L_1$ also must be.

1

There are 1 best solutions below

2
On BEST ANSWER

Let $M$ be a DFA that recognizes $L$. Modify $M$ to get a new DFA $M'$ as follows. The states, alphabet, initial state, and transition function of $M'$ are the same as for $M$. A state $q$ of $M'$ is an acceptor state of $M'$ if and only if the $0$-transition from $q$ goes to an acceptor state of $M$. Then $M'$ recognizes $L_1$.