3
$\begingroup$

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.

Let $L$ be a regular language and then let $L'$ be: $L' = \{w \in \Sigma^\star : awb \in L, a \in \Sigma, b \in \Sigma \}$ (word in $L'$ is a word from $L$ without the first and the last letter). Prove that if $L$ is regular then $L'$ is regular too.

I tried to make a new DFA inherited from DFA that accepts words in $L$ but I'm stuck on how to do this. Any help appreciated :)

$\endgroup$
2
  • $\begingroup$ can you show that, for fixed $a \in \Sigma, b \in \Sigma$, the language $\{w \in \Sigma^\star : awb \in L\}$ is regular? Then $L'$ is the union of those $\endgroup$
    – hgmath
    Mar 7, 2021 at 12:15
  • $\begingroup$ yes, I guess that makes sense... but the trouble is that i don't know exactly how to construct DFA that gets rid of the first and the last lettter, but I will think of that in that way, thanks:) $\endgroup$
    – quickMaths
    Mar 7, 2021 at 12:21

1 Answer 1

1
$\begingroup$

SKETCH: Start with a DFA $M$ for $L$. Let $q_0$ be the initial state of $M$, let $Q_1$ be the set of states of $M$ that can be reached from $q_0$ in one transition, and let $Q_a$ be the set of states of $M$ that have at least one transition to an acceptor state of $M$. Modify $M$ as follows to get an NFA $M'$:

  • Change each transition $q_0\overset{x}\longrightarrow q$ with $q\in Q_1$ to an $\epsilon$-transition $q_0\overset{\epsilon}\longrightarrow q$.
  • Let $Q_a$ be the set of acceptor states of $M'$.

Then show that the NFA $M'$ accepts $L'$.

$\endgroup$
4
  • $\begingroup$ Thank you for the response. I don't fully understand why $Q_a$ should have at least one transition to an acceptor state. Should'nt it be exactly one transition? $\endgroup$
    – quickMaths
    Mar 8, 2021 at 7:46
  • 1
    $\begingroup$ @quickMaths: No, as long as there is at least one transition out of $q$ to an acceptor state, we know that a word that takes $M$ to $q$ can be completed to a word of $L$ by adding one more character. Possibly this can happen in several different ways several different acceptor states, but that doesn’t matter; what matters is that it can happen in at least one way. $\endgroup$ Mar 8, 2021 at 7:50
  • $\begingroup$ Okay, now I see. I misread that we can have only one connection to an acceptor state and thought that we would cut off more than one letter from the end. Now that's clear. Thank you a lot. $\endgroup$
    – quickMaths
    Mar 8, 2021 at 7:56
  • $\begingroup$ @quickMaths: You’re very welcome. $\endgroup$ Mar 8, 2021 at 7:58

You must log in to answer this question.

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