0
$\begingroup$

Given that $L\subseteq\{0, 1\}^*$ is a regular language, how can I show that the language $L' =\{ w \in \{0, 1\}^∗ \mid 1w \in L \}$ is also regular?

The exercise asks me to provide a formal account of any construction used in your argument

My thoughts were to introduce two DFAs respectively for $L$ and $L'$ and then define components of $L'$.

Define the DFA $D = ( Q, E, g, q_0, F)$ for regular language $L$ where

  • $Q$ is a set of states
  • $E$ is the alphabet
  • $g$ is the transition function
  • $q_0$ is the start state
  • $F$ is the set of accept states

and define the DFA $D' = (Q', E', g', q'_0, F')$ for the language $L'$.

The main issue now is to define the components of $D'$.

Any help would be much appreciated, thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

The DFA $D'$ looks like $D$ with $g'(q'_0,1)=q_0$ and $g'(q'_0,0)=\hat q$, where $\hat q$ is a new state not in $D$. Then $D'$ should behave as $D$ when 1 is read as the first symbol.

$\endgroup$
1
  • $\begingroup$ I think you misread the question. The language $L'$ is not $\{1w \mid w \in L\}$. $\endgroup$ Jun 9, 2017 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .