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

AI Thread 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.
 

Thread 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
View full post »

Thread 'Touch-typing for programmers'

What percentage of programmers have learned to touch type? Have you? Do you think it's important, not just for programming, but for more-than-casual computer users generally? ChatGPT didn't have much on it ("Research indicates that less than 20% of people can touch type fluently, with many relying on the hunt-and-peck method for typing ."). 'Hunt-and-peck method' made me smile. It added, "For programmers, touch typing is a valuable skill that can enhance speed, accuracy, and focus. While...
View full post »

Thread 'Microsoft Technical Interview question'

I had a Microsoft Technical interview this past Friday, the question I was asked was this : How do you find the middle value for a dataset that is too big to fit in RAM? I was not able to figure this out during the interview, but I have been look in this all weekend and I read something online that said it can be done at O(N) using something called the counting sort histogram algorithm ( I did not learn that in my advanced data structures and algorithms class). I have watched some youtube...
View full post »

Similar threads

MHB Is the DFA of the language L correct?
Replies
8
Views
2K
MHB Regular Expressions Help: Find Language for DFA Drawing
Replies
13
Views
4K
MHB Proving Regularity of $L^R$ Using DFA Construction
Replies
18
Views
3K
MHB What Language Does This DFA Recognize?
Replies
10
Views
3K
MHB Creating DFA's for $\Sigma=\{0,1\}$ Languages
Replies
4
Views
2K
Given specific v, dimension of subspace of L(V, W) where Tv=0?
Replies
15
Views
2K
MHB What is the General Form of the Language Recognized by the Given Automaton?
Replies
2
Views
2K
Designing a DFA for L={vwv : v,w elements of {a,b}* and |v| =2}
Replies
1
Views
2K
Is this computability theory proof correct?
Replies
1
Views
1K
MHB Proving L is not Regular using Pumping Lemma
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top