edited by
3,575 views
4 votes
4 votes
Let us define an operation $truncate$, which removes the rightmost symbol from any string. For example, $truncate (aaaba)$ is $aaab$. The operation can be extended to languages by
$truncate (L)= $ {$truncate(w):w ∈ L$}
Show how, given a dfa for any regular language L, one can construct a dfa for $truncate (L)$.
From this, prove that if $L$ is a regular language not containing $λ$, then $truncate (L)$ is also regular.
edited by

5 Answers

5 votes
5 votes

Make all those states as final states which have a transition to the final state in the given DFA of language L.

Let's take couple of simple examples to understand it better

Example 1: Here is the DFA of Regular language $L_1 = \{ abba \}$ defined on input symbol $\Sigma = \{ a,b \}$.

To obtain a DFA of $truncate(L_1)$ we make $q_3$ as the final state, as shown below.

Example 2: Let $L_2=(aab^*)$ be a regular language with the following DFA

To obtain a DFA of $truncate(L_1)$ we not only need to make $q_1$ as the final state but $q_2$ also. This is because $q_2$ has a transition to the final state in the given DFA. Thus finally, this is what we get.


Since we can obtain a valid DFA for the truncate function from a DFA of a regular language, we can say that if the language L is regular then truncate(L) is also regular.

However, the truncate function cannot be appropriately defined for an empty string, because we will not have an alphabet to remove from the string. And this fact remains consistent with the idea presented above.

HTH

edited by
3 votes
3 votes

With a bit of intuition we can design the DFA for the truncate operation and hence prove regular language is closed under truncate operation..

Informal description of the required DFA  :

As mentioned in the question , for truncate operation , we need to remove the rightmost character from each string..So to get the rightmost character , we need to go to the final states of the present DFA(means DFA of the original language)..Now for each final state of the DFA , we need to check the two possibilities : 

Case 1 :  If the final state concerned has no self loop :

Whether the final state has self loop or not can be checked easily using the transition rules of the DFA for the concerned final state.

If at all , there is no self loop in that state , it means we have to go one state backwards and make that final state and the current state will be non final as from the new final state to old final state we have only one character which we want not to be accepted by the new DFA...Hence the old final state becomes the non final state basically..

Case 2 : If the final state has self loop :

In this case all things remain the same except that the old final state is retained as final state in the new DFA as well and the previous to final state is also made final state as in the previous case..

This we do for every final state of the original DFA..Hence truncate operation on regular language leads to regular language only.

3 votes
3 votes

truncate operation on regular language leads to regular language:- it can be proved using Right quotient rule also....

L={language on (a+b)*}

let take another language like this...

L2={a,b}

now L1/L2=represents, truncate (L);

and we know that the Regular language is closed under Right quotient operation.....????

0 votes
0 votes

Let L be a regular language. This implies that there exits a DFA say M   =  (K, S, $\delta$, q0, F) which accepts L. We shall obtain a DFA M'  =  (K, S, $\delta$, q0, F') which accepts truncated(L) from M. Make the states which reach the states in F in one transition the final states F' of M'. Clearly M¢ accepts truncated(L). Hence truncated(L) is regular.

Related questions

0 votes
0 votes
2 answers
1