GATE CSE 1997 | Question: 21

Question

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

Comments

For first in L^p  one ss’  this whole  the whole l power p belongs to L that is accepted by finite state Machine .Now then it is being split into two parts s and s’   so automatically s should  be accepted by finite automata we can make some finite automata by making the last state at which string s is ending as the final state

---

Only part a. @GO Classes @Arjun sir is this okay? @Deepak Poonia sir!

---

@yuyutsu

Answer 1

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.

Comments

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

Answer 2

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.

Comments

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.

Answer 3

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