3
$\begingroup$

"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular."

I tried going by closure properties of regular languages but got nowhere.. I said L' = {x| y is in L and xa = y, for some a in the alphabet} and didn't really know where to go from there... I also tried to argue that since L is a regular language, it can be expressed by some regex..and I wanted to show by cases that we can form a new regex by omitting the last unit of regex? But that seemed flawed. I also tried creating a skeleton dfa for L and just changing the set of accepting states to the states that transition into the previous final states.. I feel like there is a gap in my knowledge and would really appreciate it if someone could not only help me figure out the solution but also give me some advice on how to approach such problems and fill the gaps in my knowledge!

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ What went wrong with your approach with the "skeleton" in which you describe how to transform one automaton into a new one for the language without last letter? $\endgroup$ – Hendrik Jan Aug 5 '16 at 0:53
  • 1
    $\begingroup$ "if is a regular language" - Something is missing. I encourage you to edit your question to fix that. When copy-pasting, it's best provide attribution for the source. You say you tried creating a DFA for L. Please elaborate on what happened when you tried that. Why did you reject that approach? Where did you get stuck, when trying that approach? $\endgroup$ – D.W.♦ Aug 5 '16 at 0:54
  • 2
    $\begingroup$ Other approaches are also feasible, depending on the tools you are allowed to use. If you want to do it with standard closure properties it seems you need to know about morphisms and inverse morphisms. You can (in this case) also use regular expressions and a recursive way of describing the new language (which is known as structural induction). $\endgroup$ – Hendrik Jan Aug 5 '16 at 0:55
  • 1
    $\begingroup$ (Please fix missing characters in question) Approach with regex transformation seems ok, but you can't simply omit last character in regex, transformation needs to recurse into every sub-regex, that can accept rightmost character. Maybe I should write a formal answer :) $\endgroup$ – Patryk Obara Aug 5 '16 at 20:39
  • $\begingroup$ @PatrykObara, yes please! $\endgroup$ – Ryan Lee Aug 5 '16 at 23:45
5
$\begingroup$

This is just a special case of right quotient. Specifically, for a language $L$ over an alphabet $\Sigma$, this is $L / \Sigma$.

Many textbooks and course notes contain proof of regular languages' closure under right quotient. For example, here, on page 10.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for your solution, it's just that we were not taught the right quotient in class so I could not think of this approach and I believe that we were supposed to use another approach. $\endgroup$ – Ryan Lee Aug 6 '16 at 20:17
  • $\begingroup$ What you can do is, look at the technique for showing that regular expressions are closed under right quotient, and just apply that to this limited case. You can use the construction without ever mentioning right quotient. $\endgroup$ – jmite Aug 6 '16 at 20:24
2
$\begingroup$

Let's show this by transforming regular expression accepting $L$ over $\Sigma$ using function $T:X' \to X$, where $X$ is set of regular expressions, $X'$ is set of regular expressions not accepting empty words.

Smallest language not accepting empty word consists of single letter $a \in \Sigma$. In such case transformation is trivial:

$T(a) = \epsilon$

Now, if our regular expression is other regex starred, we apply transformation recursively (I will use dot to denote concatenation to distinguish it from $T$ application):

$T(R^*) = R^* \cdot T(R)$

In case regex is alternation, we go recursively into both regular expressions:

$T(R|S) = T(R)|T(S)$

Most tricky transformation is when we deal with concatenation, because we don't know if last character in word is accepted by first or second regex, we need to split this into 2 cases:

$$ T(R \cdot S) = \begin{cases} R \cdot T(S) & \text{when $ \epsilon \notin L(S) $} \\ T(R)|R \cdot T(S) & \text{when $ \epsilon \in L(S) $} \end{cases} $$

And that's it :) Proof of correctess is inductive over regex structure.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Things are a bit more complicated, since in $R^*$, the expression $R$ could represent $\epsilon$; also, $R^*$ always represents $\epsilon$. Still, the general approach seems sound. $\endgroup$ – Yuval Filmus Aug 6 '16 at 12:24
  • $\begingroup$ It's still ok, simply regex for $L$ can't be $R^*$ nor any form that might might accept $\epsilon$ (such as $R|S^*$). We don't need to worry about it, because we have $X'$ as $T$ domain. We still need this rule to handle recursive applications. $\endgroup$ – Patryk Obara Aug 6 '16 at 14:06
  • $\begingroup$ thank you! I guess I need more practice putting my thoughts into formal notation. This was very informative! $\endgroup$ – Ryan Lee Aug 6 '16 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.