-1

If I have a truncate operation defined which removes the rightmost symbol from a string ,for instance I have a string say aababb so it removes the rightmost symbol b and the output is aabab.

so how to approach this question

RADHA GOGIA
  • 197
  • A DFA implements a decision procedure. You can not solve your problem with a DFA. – wlad Apr 12 '15 at 13:59
  • As @user3491648 says, a DFA recognises a set of languages, it can not "change" a string, so what exactly are you trying to do and what is your question? – mrp Apr 12 '15 at 14:02
  • Maybe she's trying to make a Mealy machine. – MJD Apr 12 '15 at 14:19
  • 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}. – RADHA GOGIA Apr 12 '15 at 14:21
  • I am not trying to make a mealey machine ,you can check out this question in peter linz book for chapter 2 ,first exercise. – RADHA GOGIA Apr 12 '15 at 14:35

1 Answers1

1

HINT: Start with a DFA for the original language $L$, and modify it to get a DFA for the truncated language. The only part of it that you need to change is the set of acceptor (final) states.

A state should be an acceptor state in the new automaton if there is a transition from it to a state that was an acceptor state in the old one.

Brian M. Scott
  • 616,228
  • I agree with you but if there is a self loop on final state of original language itself then we should keep this state as it is. i.e we should not convert it from final to non -final state. for example $ab^*$ . If you make the initial state as only final state (as it is one step away from final state in original language) then it can not accept $ab$ or $abb$ etc. right? – ViX28 Oct 20 '16 at 06:18
  • 2
    @ViX28: If $q$ is an acceptor state in the original DFA, and there is some transition from $q$ to $q$, then $q$ will automatically remain an acceptor state in the new DFA if you follow the spoiler-protected rule. – Brian M. Scott Oct 20 '16 at 08:53