The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 votes
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where

$L^P = \left\{s \mid ss' \in L \text{ some string }s'\right\}$

$L^R = \left\{s \mid s \text{ obtained by reversing some string in }L\right\}$
asked in Theory of Computation by Veteran (59.8k points) | 1.2k views
Finding prefixes is pretty similar to what we do to find complement. Seems like only diff is in complement we mark final state as non final. Is this reasoning correct?

2 Answers

+34 votes
Best answer
Suppose we have a finite automation for $L$, then we can build a finite automation for $L^P$ by marking all the states from which final state is reachable as the final states for new automaton, the reasoning is that suppose we can reach final state $f$ form some state $q$, then that means there exists some string $s$' that takes automation from $q$ to $f$, so if there is some string s that takes automation to state $q$ from start state this string should belong to the new language $L^P$. ($L^P$ is the set of all prefix strings for the string in $L$)

Also, we can obtain an automation for $L^R$ by swapping the start and final states of original automation $L$ and by reversing all the edges in the DFA.
answered by Active (2.5k points)
edited by

reachable from final state 
should be 
from which final state is reachable rt?


yes :)

I think you forgot to reverse all edges (arcs) in the transition diagram to obtain LR

Second language is reversal. What first language is saying here. ?
it has given a hint - $p$- all prefix strings.
More appropriately, to convert a dfa M (with L(M) = L) into Mp (with L(Mp) = Lp), all those internal states should be made final states through which a path from the initial state to the original final state exists.


sir pls explaim first language with example

While finding reverse of a  regular language using the method defined above i.e. reversing all the transitions and swapping start and final states.... my questions is what if we have multiple final states, then if we try to find reverse of regular language by finite state automata we will get multiple start states which is not possible in case of Regular languages...
@pallaviamu, make one more state as final state and connect all final state with epsilon move.
very nice approach omesh pandita sir

@set2018 first part says String s belongs to language L(P) if some string s' is concatenated to it and complete string ss' belongs to L. Now you take any string s and append to it s' such that in original DFA L it reaches to final state. This is nothing but all prefix of strings of original language.

+4 votes

Since L is accepted by an FSA, it is a regular language

$L^P$ is the set of all prefix strings of $S^{'}$ in L. $L^R$ is the reverse of some string in L. By closure properties of languages, both $L^P$ and $L^R$ are regular. For every regular language there is a finite state automaton (FSA) that accepts the language. Therefore, $L^P$ and $L^R$ are also accepted by some finite state machines.

answered by Active (4.1k points)
edited by
You applied closure properties -- is enough for objective exams. But here the question asks for proof -- that will be required while attending Interviews at IITs/TIFR/IIITs etc.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,129 questions
53,252 answers
70,506 users