CMI2011-B-04b

Question

Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\}^* \mid \text{ reverse}(w) \in L \}$ - here $reverse(w)$ denotes the string $w$ read in reverse. For example $reverse(0001) = 1000$.

1. Show that the language $L.L^R \triangleq \{x \in \{0, 1\}^* | \exists y,z$ where $x=yz, \: y \in L, \: z \in L^R \}$ is regular. How can you use $N$ to construct an automata for $L.L^R$?

Answer 1

For the 1st part, 

Regular languages are closed under Reversal ($L^R$) and Concatenation ($L.L'$) operations.

Formally,

$L$ is Regular $\iff$ $L^R$ is Regular
$L$ and $L'$ are Regular $\implies$ $L.L'$ is Regular

So, $L$ and $L^R$ are Regular $\implies$ $L.L^R$ is Regular

(You can go through the proofs for these 2 properties from any standard book, but I don't think it is required to write for this question)

 

For 2nd part,

Steps to Contruct FA $N'$ for $L^R$ given a FA $N$ for $L$: (from my answer for 2011-B-04a)

1. Convert the NFA $N$ to a DFA using the subset construction algorithm. Let the resulting DFA be $D$.
2. To build an NFA $N'$ to accept $L^R$, we do the following:

•     Reverse the direction of all edges in the transition diagram. 
  That is, replace every transition $\delta(q_i, a) = q_j$, where $a \in \{0,1\}$, with  $\delta^R(q_j, a) = q_i$.
•     The original start state of $D$ becomes the new final state in $N'$.
• The final state(s) in $D$ become the new start state(s) in $N'$. If $|F| > 1$, add a new start state $q_0$ and add $\epsilon$-transitions from $q_0$ to all original final states in $D$.

Now we have finite automata for $L$ and $L^R$, which are $N$ and $N'$ respectively.

 

We make a new FA say $M$ for accepting $L.L^R$, which has following properties:

• M has all the states from $N$ and $N'$. If $i$ and $j$ are number of the states in $N$ and $N'$, then $M$ will have $i+j$ states.
• The start state of $M$ is the original start state ($q_0$) of $N$.
• The only final state(s) of $M$ are the original final state(s) of $N'$.
• We add $\epsilon$-Transitions from every state in $M$ which were originally final state(s) in $N$ to the state which was originally start state in $N'$.

 

So what really happens in this new FA $M$? 

I will try to to give an informal proof of working for $M$.

 

For a string satisfying the language $L.L^R$ we need to show that it reaches one of the final state of $M$.

First the string moves to a state which was a final state in $N$, satisfying the condition for language $L$.

Then via a $\epsilon$-transition,it reaches a state in $M$ which was a start state in $N'$, from there satifying the condition for language $L^R$, the string reaches one of final states in $M$, as they were also final states in $N'$.

 

I hope this answer was helpful!

Answer 2

Yes We can form a NFA for L.L^R . So, it is regular

Comments

@Arjun Sir @Praveen sir  plz chk it

---

What is the NFA doing?

---

you have created NFA and you don't know what it is doing  ....Lol