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

Expert Solution

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

Here, I've chosen states q_ij 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 q_i6 to q_i0 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 q_6j to q_0j when an a is encountered.

q₀₀ 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.

venereology answered 1 year ago

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.

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)

(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).

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

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

PYTHON PLEASE: Construct a class “Monster” with the following attributes: self.name (a string) self.type (a string,...

PYTHON PLEASE: Construct a class “Monster” with the following attributes: self.name (a string) self.type (a string, default is ‘Normal’) self.current_hp (int, starts out equal to max_hp) self.max_hp (int, is given as input when the class instance is created, default is 20) self.exp (int, starts at 0, is increased by fighting) self.attacks (a dict of all known attacks) self.possible_attacks (a dictionary of all possible attacks) The dictionary of possible_attacks will map the name of an attack (the key) to how many...

Use a mathematical induction for Prove a^(2n-1) + b^(2n-1) is divisible by a + b, for...

Use a mathematical induction for Prove a^(2n-1) + b^(2n-1) is divisible by a + b, for n is a positive integer

Question