5,210 views
41 votes
41 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\}$

3 Answers

Best answer
59 votes
59 votes
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.
edited by
10 votes
10 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.

edited by
0 votes
0 votes
(A)

Let us assume the DFA that accepts L, D(L)=(Q,Σ,q0,δ,F)

The extended transition function for DFA, D(L) is  δ*

Given that ss’ ∈ L,

So as a valid string for D(L),  δ*(q0, ss’)  ∈ Q (To be precise F, but as F is a subset of Q, Q also works)

s ∈ L(P) so if we put s into D(L), δ*(q0, s)  ∈ Q,

as Q is a finite set we can see that every string in L(P) leads us to a single state, and all the strings combined can lead us to a subset of Q

So a DFA for L(P) can be created.

 

(B)

L(R) can be obtained by swapping the initial and final states and reversing the edges. If there are multiple final states, first create an NFA with single final state(new final state with ∈ transitions from all final states) then convert that to a DFA.

Related questions

24 votes
24 votes
1 answer
3
Kathleen asked Sep 29, 2014
14,260 views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...
21 votes
21 votes
2 answers
4
go_editor asked Oct 14, 2015
7,707 views
Following is a state table for time finite state machine.$$\begin{array}{|l|ll|}\hline \textbf{Present State} & \textbf{Next State Output} \\ & \textbf{Input- 0} & \t...