Question

In: Computer Science

construct a DFA to check if a string containing a,b and no.of a's is divisible by...

construct a DFA to check if a string containing a,b and no.of a's is divisible by 5 and no.of b's is divisible by 7

Solutions

Expert Solution

So basically to design a DFA, we first need to decide what will be the states.

Here, I've chosen states qij which denotes a state where ( number of a's ) % 5 = i and  ( number of b's ) % 7= j

So basically we move from one state to another according to the character being considered.

The logic for moving from qi6 to qi0 when b is encountered is simple as, that if a number mod 7 is 6 that means adding 1 more, will make it divisible by 7 and resulting in 0 as remainder.

Similar is the reason for q6j to q0j when an a is encountered.

q00 is the finalstate as only there, the number of a's are divisible by 5 and number of b's are divisible by 7.

Another than that, it is a normal DFA and all conditions are understandable.


Related Solutions

Given two DFAs, A and B, show that you can construct a DFA C such that...
Given two DFAs, A and B, show that you can construct a DFA C such that L(C) = ∅ if and only if L(A) ⊆ L(B). Prove that your construction works by proving the if and only if statement.
Construct a dfa that accepts strings on {0, 1} if and only if the value of...
Construct a dfa that accepts strings on {0, 1} if and only if the value of the string, interpreted as a binary representation of an integer, is zero modulo five. For example, 0101 and 1111, representing the integers 5 and 15, respectively, are to be accepted.
Construct NFA of following languages and convert it to equivalent DFA. The set of all binary...
Construct NFA of following languages and convert it to equivalent DFA. The set of all binary strings such that 3th symbol from right end is 0.
Construct a DFA machine to recognize the language of all binary numbers which are a multiple...
Construct a DFA machine to recognize the language of all binary numbers which are a multiple of 5. L = { w belongs {0,1}* : w is a binary number and is a multiple of 5} Example: 101 belongs to L; 1010 belongs to L; 110 doesn't belong to L.
C++ function to a string into enum function to a enum into a string check valid...
C++ function to a string into enum function to a enum into a string check valid / loop ( asking a couple of times until answer invaild) For example Enum Fruit ( APPLE, STRAWBERRY, BLUEBERRY, BLACKBERRY) output should be what is your favorit fruit? : strawberry you will have STRAWBERRY. what is your favorite fruite : peach invaild TIA
Draw DFA C = { w is an element of {a,b}* and #a(w) is even and...
Draw DFA C = { w is an element of {a,b}* and #a(w) is even and #b(w) us a multiple of 3)
- Give state diagram of DFA recognizing L={w | w is 0,1-string, and contains 3k 0s...
- Give state diagram of DFA recognizing L={w | w is 0,1-string, and contains 3k 0s and 2m 1s for some integers k and m at least 0}. For examples, 0010111 is in L, but 010011 is not in L. The first string contains 3 0s and 4=2x2 1s, but the second string has an odd number of 1s.
P1. Construct the tree with post-order traversal string = i b d a h g c...
P1. Construct the tree with post-order traversal string = i b d a h g c f, and in-order traversal string = b i a d f g h c. P2. Construct the tree with pre-order traversal string = 10, 20, 40, 50, 80, 60, 70, 90, and in-order traversal string = 40, 50, 20, 10, 80, 70, 90, 60.
(10 marks) Write a function to check whether string s1 is a substring of string s2....
Write a function to check whether string s1 is a substring of string s2. The function returns the first index in s2 if there is a match. Otherwise, return -1. For example, the function should return 2 if s1 is "to" and s2 is "October". If s1 is "andy" and s2 is "candy", then the function should return 1. The function prototype is as follows: int indexOf(const char *s1, const char *s2).
Using JES/ Jython Function Name: decoder() Parameters: message1-string containing first part of secret message message2-string containing...
Using JES/ Jython Function Name: decoder() Parameters: message1-string containing first part of secret message message2-string containing second part of secret message Write a function that decodes them by retrieving every other character from both encrypted messages. Test Cases: >>>decoder("Rsupnk","oFpansot") Run Fast >>>decoder("Fkrneoem ktthpes","eAvleiselnos") Free the Aliens
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT