The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
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


plzz rectify my doubt
asked in Theory of Computation by (275 points)
retagged by | 67 views
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 (15.5k points)

Related questions

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
49,403 questions
53,576 answers
70,852 users