1,857 views

1 Answer

Best answer
6 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
Position:
Show:

Related questions

0 0 votes
0 0 answers
581
581 views
Dknights asked Nov 9, 2022
581 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)* } RE d...
0 0 votes
1 answers 1 answer
794
794 views
aditykansara asked Jun 23, 2018
794 views
How to construct an automata with even number of a's OR odd number of b's?
4 4 votes
1 1 answer
5.4k
5.4k views
Deepthi_ts asked Apr 17, 2017
5,360 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 – 3CNFA – 3,...
0 0 votes
1 1 answer
743
743 views
Mubashirulislam asked Mar 20, 2017
743 views
Which automata define the same language? Note: (b) and (d) use transitions on strings. You may assume that there are non-accepting intermediate states, not shown, that ar...