MHB What are the DFA configurations for L={w:${n}_{a}$(w) mod3 < 1} on $\sum$={a,b}?

Click For Summary
The discussion focuses on constructing a deterministic finite automaton (DFA) for the language L defined over the alphabet {a, b}, where the condition is that the number of occurrences of the symbol 'a' in any string w must satisfy the condition n_a(w) mod 3 < 1. The solution involves creating three states {0, 1, 2} that represent the remainders when the count of 'a's is divided by 3. The automaton transitions to the next state upon reading an 'a' while remaining in the same state when reading a 'b'. The key point is that the accepting state corresponds to the condition mod 3 = 0, which indicates that the number of 'a's is a multiple of 3. The original poster successfully determined the accepting states after interpreting the condition correctly.
comfortablynumb
Messages
3
Reaction score
0
Find dfa's for the following language on
$\sum$={a,b};

c)
L={w:${n}_{a}$(w) mod3 < 1;
 
Technology news on Phys.org
You need three states $\{0,1,2\}$ that will correspond to the remainder when the number of read symbols $a$ is divided by 3. When the automaton reads a $b$, it remains in the same state. When the automaton reads an $a$, it moves to the next state. Can you figure out which states should be accepting?
 
Thank you, Evgeny.Makarov, I figured it out. I treated mod3<1 as mod3=0 and did it. I was okay figuring out accepting states.
 

Similar threads

  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 13 ·
Replies
13
Views
4K
  • · Replies 18 ·
Replies
18
Views
3K
  • · Replies 10 ·
Replies
10
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
Replies
15
Views
2K
Replies
2
Views
2K
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K