2,297 views
1 votes
1 votes

A regular lang is represented by a DFA. To find the reverse of the lang, we do the following:

                                  Change directions of arrows of state transitions and also interchange final <-> non-final states.

A regular lang is represented by a DFA. To find the complement of the lang, we do the following:

                                 Only interchange final <-> non-final states but arrows of state transition are kept same.

Am I correct? 

Now in case of reverse, previous final state would be new start state after reversing. So if there were two final states before then after reversing should both the states be "start state"?

1 Answer

6 votes
6 votes

Yes, you are right about that, but I would suggest that you please follow a much more logical approach toward these kind of questions, don't memorize those tricks, instead keep this thing in mind:- 
say for example a language is in the form, L={ anbn ; n $\leq$ 1}

Reversal:- L={ bnan ; n $\leq$ 1}
(Just reverse the strings in the given language OR LR)

Complement :- treat the given Language such that , it can accept anything except what condition is specified in the language, therefore It can accept everything except {ab, aabb, aaabbb...}that is, it can't accept equal number of a's and b's in a string.

(Or simply LC = $\sum$ * - L)

 If you still want a direct answer using tricks only, you can refer :- https://www.youtube.com/watch?v=em-lZgQeDlI
Hope this Helps :)

edited by

Related questions

0 votes
0 votes
0 answers
2
Tuhin Dutta asked Dec 4, 2017
577 views
$ L = \{ wxwy \ | \ \ x,y,w \ \ \epsilon\ ( a + b )^+ \} $Draw the DFA and also write the Reg exp for the above language.
0 votes
0 votes
0 answers
3
VikramRB asked Jan 5, 2019
4,220 views
The Minimum DFA that accepts the given language is ____L = { w | w is any string not in a*b*}
0 votes
0 votes
1 answer
4
Mk Utkarsh asked Dec 18, 2017
457 views
Construct a finite automata from 0*1*1 + 11*0*1