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

Next > < Previous

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.

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

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

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.

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

I wrote this program to check a string is palindrome or not. but in both cases,...

I wrote this program to check a string is palindrome or not. but in both cases, it gives me palindrome. could someone help me with this program? it has an error I couldn't find. when I run the code and give a string, in both cases it gives me palindrome. for example if I give Pop it says it is a palindrome but if I give Salima, it also says palindrome. #include<string> #include <iostream> using namespace std; class PString:public string...

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

Suppose you are given a string containing only the characters ( and ). In this problem,...

Suppose you are given a string containing only the characters ( and ). In this problem, you will write a function to determine whether the string has balanced parentheses. Your algorithm should use no more than O (1) space beyond the input; any algorithms that use space not in O (1) will receive half credit at most. Any solutions that always return true (or always return false) or otherwise try to game the distribution of test cases will receive zero...

Subjects