The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
746 views
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.5k points) | 746 views

2 Answers

+29 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
+1

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

 

0
yes :)
+1

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

0
Second language is reversal. What first language is saying here. ?
0
it has given a hint - $p$- all prefix strings.
0
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.
0

 Arjun

sir pls explaim first language with example

0
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...
0
@pallaviamu, make one more state as final state and connect all final state with epsilon move.
0
very nice approach omesh pandita sir
+3 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 (4k points)
edited by
+1
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.


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

39,848 questions
46,815 answers
141,153 comments
59,066 users