in Theory of Computation retagged by
261 views
0 votes
0 votes
Suppose we have a FA  N(a)mod3=0 In this FA the initial state and final state is same

If we will reverse this FA  the state will be remain same or not that initial state and final state is going to be the same or not

and after reversing the string the strings are not getting reverse it will accept only

$L=\{\epsilon,b,bb,bbbb,bbb,bbbbbb.............\}$

plzz rectify my doubt
in Theory of Computation retagged by
261 views

1 comment

Steps to find reverse of language :-

1. Reverse all arrows

2.Exchange final and start states

3.IF multiple start states after step 2,combine them into 1 using e-moves
0
0

1 Answer

0 votes
0 votes

$\Sigma = {a,b}$ 
$L$ = {$\epsilon$, b ,bb,aaa,bbb, aaab,aaabb,aaaaaa.....}
i.e L= N(a) is multiple of 3.
Consider a string $aababb$ .. It's reverse - $bbabaa$ Now even after reversal, the number of $a's$ remains same in the string. 
This shows that Language will remain same so it's NFA will also remain same. $L = rev(L)$

Now just stick to the rules. 
Steps to find NFA for $rev(L)$ -
1. Reverse all the arrows.
2. Interchange initial state and final state.
Note- If multiple final states are present in NFA then first convert it into NFA having single final state by adding $\epsilon$ moves.