1,158 views
2 votes
2 votes
Symbols are a and b

Fund DFA where...

(N(a) - N(b)) mod 3 > 1

1 Answer

Best answer
6 votes
6 votes

possible values of $x \mod 3 = 0,1,2$

$\\ L = \left \{ w|( \ n_a(w) - n_b(w) \ ) \mod 3 > 1 \right \} \\ \\ L = \left \{ w|( \ n_a(w) - n_b(w) \ ) \mod 3 = 2 \right \}$

How the edges are forming ,

Few examples : at first one character strings w = 'a' or w = 'b'

$n_a(w) - n_b(w) = \ ?$

if w = 'a' then

$n_a(w) = 1 \ \ , \ n_b(w) = 0 \\ \\ => 1 - 0 = 1 \\ \\=> (1) \mod 3 = +1$

i.e. we make a transition from state(0) to state(1) for signle character string 'a'

if w = 'b' then 

$n_a(w) = 0 \ \ , \ n_b(w) = 1 \\ \\ => 0 - 1 = -1 \\ \\=> (-1) \mod 3 = +2$

i.e. we make a transition from state(0) to state(2) for signle character string 'b'

We finished all one character string , now for two character string we take (for example) w = 'ab'

if w = 'ab' then 

$n_a(w) = 1 \ \ , \ n_b(w) = 1 \\ \\ => 1 - 1 = 0 \\ \\=> (0) \mod 3 = 0$

i.e. read 'a' move from state(0) to state(1) [ result 1]

and read 'b' move from state(1) to state(0) 

etc.

We go on checking for all two character strings and move to the resultant state in two steps, by utilizing one character string results.

Likewise calculate for three character strings. And by this time all remaining edges are fiiled up and we do not need to check for

$|w| > 3$.

edited by

Related questions

0 votes
0 votes
0 answers
1
Dknights asked Nov 9, 2022
375 views
Regular Expression for accepting the language L = { 0^n1^m | n+m=even }I got this solution – (00)*(11)*+0(00)*1(11)*please point out how this – {(00)* (01)* (11)* } ...
0 votes
0 votes
1 answer
2
aditykansara asked Jun 23, 2018
522 views
How to construct an automata with even number of a's OR odd number of b's?
3 votes
3 votes
1 answer
3
Deepthi_ts asked Apr 17, 2017
4,204 views
Consider regular expression r, where r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA respectively are:ANFA – 3, DFA – 4BNFA – 3, DFA – 3...