The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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\}$

$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\}$

+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.

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.

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

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...

+1

@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.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,129 questions

53,252 answers

184,785 comments

70,506 users