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

  • Context: MHB 
  • Thread starter Thread starter comfortablynumb
  • Start date Start date
  • Tags Tags
    Computation Dfa Theory
Click For Summary
SUMMARY

The discussion focuses on constructing a Deterministic Finite Automaton (DFA) for the language L={w:${n}_{a}$(w) mod3 < 1} over the alphabet $\sum$={a,b}. The DFA requires three states, labeled {0, 1, 2}, representing the remainders when the count of 'a' symbols is divided by 3. The automaton remains in the same state upon reading 'b' and transitions to the next state upon reading 'a'. The solution involves treating the condition mod3<1 as equivalent to mod3=0, leading to the identification of the appropriate accepting states.

PREREQUISITES
  • Understanding of Deterministic Finite Automata (DFA)
  • Knowledge of modular arithmetic, specifically mod3 operations
  • Familiarity with state transition diagrams
  • Basic concepts of formal languages and automata theory
NEXT STEPS
  • Study the construction of DFAs for different languages using tools like JFLAP
  • Explore the implications of state transitions in DFAs with varying input symbols
  • Learn about the minimization of DFAs and its applications
  • Investigate the relationship between regular expressions and DFAs
USEFUL FOR

This discussion is beneficial for computer science students, automata theorists, and software engineers involved in compiler design or formal language processing.

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