Construct the Moore Machines that will count occurrences of substring 'ab' over the input ∑ = {a,b} and convert into Mealy Machine.
Question
Construct the Moore Machines that will count occurrences of substring 'ab' over the input ∑ = {a,b} and convert into Mealy Machine.
Solution
Step 1: Define the Moore Machine
A Moore machine can be defined as a 6-tuple (Q, ∑, δ, X, Λ, G) where:
- Q is a finite set of states.
- ∑ is a finite input alphabet.
- δ: Q x ∑ → Q is the transition function.
- X is the set of output symbols.
- Λ: Q → X is the output function.
- G is the initial state.
Step 2: Construct the Moore Machine
For the given problem, we need to count occurrences of substring 'ab' over the input ∑ = {a,b}. The Moore machine M can be defined as follows:
- Q = {q0, q1, q2}, where q0 is the initial state.
- ∑ = {a, b}
- δ is defined as:
- δ(q0, a) = q1
- δ(q0, b) = q0
- δ(q1, a) = q1
- δ(q1, b) = q2
- δ(q2, a) = q1
- δ(q2, b) = q0
- X = {0, 1}
- Λ is defined as:
- Λ(q0) = 0
- Λ(q1) = 0
- Λ(q2) = 1
Step 3: Convert the Moore Machine to a Mealy Machine
A Mealy machine can be defined as a 6-tuple (Q, ∑, δ, X, Λ', q0) where:
- Q is a finite set of states.
- ∑ is a finite input alphabet.
- δ: Q x ∑ → Q is the transition function.
- X is the set of output symbols.
- Λ': Q x ∑ → X is the output function.
- q0 is the initial state.
The conversion from a Moore machine to a Mealy machine can be done by changing the output function Λ to Λ' such that for each transition δ(q, a) = p in the Moore machine, we define Λ'(q, a) = Λ(p) in the Mealy machine.
So, the Mealy machine M' equivalent to the Moore machine M is:
- Q = {q0, q1, q2}, where q0 is the initial state.
- ∑ = {a, b}
- δ is the same as in M.
- X = {0, 1}
- Λ' is defined as:
- Λ'(q0, a) = Λ(q1) = 0
- Λ'(q0, b) = Λ(q0) = 0
- Λ'(q1, a) = Λ(q1) = 0
- Λ'(q1, b) = Λ(q2) = 1
- Λ'(q2, a) = Λ(q1) = 0
- Λ'(q2, b) = Λ(q0) = 0
This Mealy machine will count occurrences of substring 'ab' over the input ∑ = {a,b}.
Similar Questions
Construct the moore machine of {a,b} to count the number ofoccurrences of the substring “ab”.
Compatible StringsCompatible Strings Two strings A and B comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:Select a prefix from the string A, and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example, if the string is ashzb and we select the prefix ash then we can convert it to bti by increasing the alphabetical value by 1. If we select the prefix ashzb, then it will be converted into btiac. Your task is to determine if given strings A and B are compatible. Input formatRead N.Read N pairs of strings, each in a separate line . Output formatFor each pair of input strings,print YES if string A can be converted to string B, otherwise print NO. SAMPLE INPUT3abacacdbdagodzjneaaqlmcmmo SAMPLE OUTPUTYESNONO Explanation for first pair of strings:The string abaca can be converted to bcbda in one move and to cdbda in the next move. No restriction on the number of moves.
Compatible StringsCompatible Strings Two strings A and B comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:Select a prefix from the string A, and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example, if the string is ashzb and we select the prefix ash then we can convert it to bti by increasing the alphabetical value by 1. If we select the prefix ashzb, then it will be converted into btiac. Your task is to determine if given strings A and B are compatible. Input formatRead N.Read N pairs of strings, each in a separate line . Output formatFor each pair of input strings,print YES if string A can be converted to string B, otherwise print NO. SAMPLE INPUT3abacacdbdagodzjneaaqlmcmmo SAMPLE OUTPUTYESNONO
Compatible StringsCompatible Strings Two strings A and B comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:Select a prefix from the string A, and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example, if the string is ashzb and we select the prefix ash then we can convert it to bti by increasing the alphabetical value by 1. If we select the prefix ashzb, then it will be converted into btiac. Your task is to determine if given strings A and B are compatible. Input formatRead N.Read N pairs of strings, each in a separate line . Output formatFor each pair of input strings,print YES if string A can be converted to string B, otherwise print NO. SAMPLE INPUT3abacacdbdagodzjneaaqlmcmmo SAMPLE OUTPUTYESNONO Explanation for first pair of strings:The string abaca can be converted to bcbda in one move and to cdbda in the next move. No restriction on the number of moves
Compatible Strings Two strings A and B comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:Select a prefix from the string A, and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example, if the string is ashzb and we select the prefix ash then we can convert it to bti by increasing the alphabetical value by 1. If we select the prefix ashzb, then it will be converted into btiac. Your task is to determine if given strings A and B are compatible. Input formatRead N.Read N pairs of strings, each in a separate line . Output formatFor each pair of input strings,print YES if string A can be converted to string B, otherwise print NO. SAMPLE INPUT3abacacdbdagodzjneaaqlmcmmo SAMPLE OUTPUTYESNONO Explanation for first pair of strings:The string abaca can be converted to bcbda in one move and to cdbda in the next move. No restriction on the number of moves.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.