The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
50 views
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
asked in Theory of Computation by (153 points)
retagged by | 50 views
0
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

1 Answer

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.

answered by Boss (12k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,963 questions
45,465 answers
131,322 comments
48,378 users