Designing a Deterministic Finite Automaton for Binary Input and Output Sequences

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Machine
In summary, the automaton depicted in the state diagram is a Deterministic Finite Automaton with three states.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

A dfa with three states has as input and output alphabet the set $\{0,1\}$.
Given the following input sequence and the corresponding output sequence , we should determine the automaton.

$ \text{ Input }: 00010101 \\ \text{Output: } 011001110$

First of all, the output should have a typo and we should ignore the last 0, so that the number of digits of the input and the output sequence is the same. Right?

Secondly, could you give me a hint how to draw such a deterministic automaton?
 
Technology news on Phys.org
  • #2
evinda said:
Hello! (Wave)

A dfa with three states has as input and output alphabet the set $\{0,1\}$.
Given the following input sequence and the corresponding output sequence , we should determine the automaton.

$ \text{ Input }: 00010101 \\ \text{Output: } 011001110$

First of all, the output should have a typo and we should ignore the last 0, so that the number of digits of the input and the output sequence is the same. Right?

Secondly, could you give me a hint how to draw such a deterministic automaton?

Hey evinda! (Smile)

Let's assume for now that it's a typo, or otherwise that we output $0$ when we enter the final state.
And let's assume we have no restriction on the number of states.
Then we can draw the following state diagram (using the new tikz picture functionality :cool:):
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick, bend left]
%preamble \usetikzlibrary{arrows,automata}
\tikzstyle{every state}=[top color=yellow!30!white,bottom color=yellow,draw=orange,text=black]

\node[initial,state] (A) {A};
\node[state] (B) [right of=A] {B};
\node[state] (C) [right of=B] {C};
\node[state] (D) [right of=C] {D};
\node[state] (E) [right of=D] {E};
\node[state] (F) [right of=E] {F};
\node[state] (G) [right of=F] {G};
\node[state] (H) [right of=G] {H};
\node[state,accepting](I) [right of=H] {/0};

\path (A) edge node {0/0} (B)
(B) edge node {0/1} (C)
(C) edge node {0/1} (D)
(D) edge node {1/0} (E)
(E) edge node {0/0} (F)
(F) edge node {1/1} (G)
(G) edge node {0/1} (H)
(H) edge node {1/1} (I);
\end{tikzpicture}

Can we reduce the number of states? (Wondering)
 
  • #3
I like Serena said:
Hey evinda! (Smile)

Let's assume for now that it's a typo, or otherwise that we output $0$ when we enter the final state.
And let's assume we have no restriction on the number of states.
Then we can draw the following state diagram (using the new tikz picture functionality :cool:):
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick, bend left]
\tikzstyle{every state}=[top color=Goldenrod1!30!white,bottom color=Goldenrod1,draw=DarkOrange1,text=black]

\node[initial,state] (A) {};
\node[state] (B) [right of=A] {};
\node[state] (C) [right of=B] {};
\node[state] (D) [right of=C] {};
\node[state] (E) [right of=D] {};
\node[state] (F) [right of=E] {};
\node[state] (G) [right of=F] {};
\node[state] (H) [right of=G] {};
\node[state,accepting](I) [right of=H] {/0};

\path (A) edge node {0/0} (B)
(B) edge node {0/1} (C)
(C) edge node {0/1} (D)
(D) edge node {1/0} (E)
(E) edge node {0/0} (F)
(F) edge node {1/1} (G)
(G) edge node {0/1} (H)
(H) edge node {1/1} (I);
\end{tikzpicture}

Can we reduce the number of states? (Wondering)

The dfa you drew is equal to the following one, right?View attachment 6077

Can we make further changes? (Thinking)
 

Attachments

  • dfd.png
    dfd.png
    3 KB · Views: 76
  • #4
evinda said:
The dfa you drew is equal to the following one, right?

Yes. Although we don't have a final state anymore now... :eek:

Can we make further changes? (Thinking)

I think so.
I've added letters to my previous post for ease of reference.
I think we can collapse B, C, D, and E to a single state, since the transitions between them are uniquely the same. (Thinking)
 
  • #5
I like Serena said:
Yes. Although we don't have a final state anymore now... :eek:

I think that when we have also outputs the existence of final states is not necessary, is it?

I like Serena said:
I think so.
I've added letters to my previous post for ease of reference.
I think we can collapse B, C, D, and E to a single state, since the transitions between them are uniquely the same. (Thinking)

The transitions have as input and output $0/1, 0/1, 1/0$. Why can we collapse B, C, D, and E to a single state? I haven't really understood it... (Worried)
 
  • #6
evinda said:
I think that when we have also outputs the existence of final states is not necessary, is it?

The transitions have as input and output $0/1, 0/1, 1/0$. Why can we collapse B, C, D, and E to a single state? I haven't really understood it... (Worried)

I like Serena said:
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick, bend left]
%preamble \usetikzlibrary{arrows,automata}
\tikzstyle{every state}=[top color=yellow!30!white,bottom color=yellow,draw=orange,text=black]

\node[initial,state] (A) {A};
\node[state] (B) [right of=A] {B};
\node[state] (C) [right of=B] {C};
\node[state] (D) [right of=C] {D};
\node[state] (E) [right of=D] {E};
\node[state] (F) [right of=E] {F};
\node[state] (G) [right of=F] {G};
\node[state] (H) [right of=G] {H};
\node[state,accepting](I) [right of=H] {/0};

\path (A) edge node {0/0} (B)
(B) edge node {0/1} (C)
(C) edge node {0/1} (D)
(D) edge node {1/0} (E)
(E) edge node {0/0} (F)
(F) edge node {1/1} (G)
(G) edge node {0/1} (H)
(H) edge node {1/1} (I);
\end{tikzpicture}

Can we reduce the number of states? (Wondering)

Let's start from the left, and let's try to collapse some of the states.
Suppose we try to collapse A and B, then we'll get:
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick]
%preamble \usetikzlibrary{arrows,automata}
\tikzstyle{every state}=[top color=yellow!30!white,bottom color=yellow,draw=orange!80!black,text=black]

\node[initial,state] (AB) {AB};
\node[state] (C) [right of=AB] {C};
\node[state] (D) [right of=C] {D};
\node[state] (E) [right of=D] {E};
\node[state] (F) [right of=E] {F};
\node[state] (G) [right of=F] {G};
\node[state] (H) [right of=G] {H};
\node[state,accepting](I) [right of=H] {/0};

\path (AB) edge[loop above] node {0/0} (AB)
(AB) edge[bend left] node {0/1} (C)
(C) edge[bend left] node {0/1} (D)
(D) edge[bend left] node {1/0} (E)
(E) edge[bend left] node {0/0} (F)
(F) edge[bend left] node {1/1} (G)
(G) edge[bend left] node {0/1} (H)
(H) edge[bend left] node {1/1} (I);
\end{tikzpicture}

Is this the same state machine?
If so, can we collapse C to AB in the same way, or will that introduce a conflict? (Wondering)
 
  • #7
I like Serena said:
Let's start from the left, and let's try to collapse some of the states.
Suppose we try to collapse A and B, then we'll get:
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick]
%preamble \usetikzlibrary{arrows,automata}
\tikzstyle{every state}=[top color=yellow!30!white,bottom color=yellow,draw=orange!80!black,text=black]

\node[initial,state] (AB) {AB};
\node[state] (C) [right of=AB] {C};
\node[state] (D) [right of=C] {D};
\node[state] (E) [right of=D] {E};
\node[state] (F) [right of=E] {F};
\node[state] (G) [right of=F] {G};
\node[state] (H) [right of=G] {H};
\node[state,accepting](I) [right of=H] {/0};

\path (AB) edge[loop above] node {0/0} (AB)
(AB) edge[bend left] node {0/1} (C)
(C) edge[bend left] node {0/1} (D)
(D) edge[bend left] node {1/0} (E)
(E) edge[bend left] node {0/0} (F)
(F) edge[bend left] node {1/1} (G)
(G) edge[bend left] node {0/1} (H)
(H) edge[bend left] node {1/1} (I);
\end{tikzpicture}

Is this the same state machine?
If so, can we collapse C to AB in the same way, or will that introduce a conflict? (Wondering)

Sorry, that was not correct, because now it's ambiguous where 0 should go in state AB.
Instead it should be:
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick]
%preamble \usetikzlibrary{arrows,automata}
\tikzstyle{every state}=[top color=yellow!30!white,bottom color=yellow,draw=orange!80!black,text=black]

\node[initial,state] (A) {A};
\node[state] (BCD) [right of=A] {BCD};
\node[state] (E) [right of=BCD] {E};
\node[state] (F) [right of=E] {F};
\node[state] (G) [right of=F] {G};
\node[state] (H) [right of=G] {H};
\node[state,accepting](I) [right of=H] {/0};

\path (A) edge[bend left] node {0/0} (BCD)
(BCD) edge[loop above] node {0/1} (BCD)
(BCD) edge[bend left] node {1/0} (E)
(E) edge[bend left] node {0/0} (F)
(F) edge[bend left] node {1/1} (G)
(G) edge[bend left] node {0/1} (H)
(H) edge[bend left] node {1/1} (I);
\end{tikzpicture}
How can we continue? (Wondering)
 
  • #8
I like Serena said:
Sorry, that was not correct, because now it's ambiguous where 0 should go in state AB.
Instead it should be:
\begin{tikzpicture}[->, >=stealth', shorten >=1pt, auto, node distance=2cm, semithick]
\tikzstyle{every state}=[top color=Goldenrod1!30!white,bottom color=Goldenrod1,draw=DarkOrange1!80!black,text=black]

\node[initial,state] (A) {A};
\node[state] (BCD) [right of=A] {BCD};
\node[state] (E) [right of=BCD] {E};
\node[state] (F) [right of=E] {F};
\node[state] (G) [right of=F] {G};
\node[state] (H) [right of=G] {H};
\node[state,accepting](I) [right of=H] {/0};

\path (A) edge[bend left] node {0/0} (BCD)
(BCD) edge[loop above] node {0/1} (BCD)
(BCD) edge[bend left] node {1/0} (E)
(E) edge[bend left] node {0/0} (F)
(F) edge[bend left] node {1/1} (G)
(G) edge[bend left] node {0/1} (H)
(H) edge[bend left] node {1/1} (I);
\end{tikzpicture}
How can we continue? (Wondering)

But now after we have printed 0 after giving 0, we can give how many 0s we want and the machine will print 1. Doesn't this matter? (Thinking)
 
  • #9
evinda said:
But now after we have printed 0 after giving 0, we can give how many 0s we want and the machine will print 1. Doesn't this matter? (Thinking)

No, because we're given what the input is. (Shake)
We just have to make it match the output without ambiguity.
 
  • #10

Attachments

  • dfan.png
    dfan.png
    3.3 KB · Views: 85
  • #11
If the input is $000101010$ and the output this : $011001110$ the desired dfa is of the following form, right?

View attachment 6093
 

Attachments

  • dfad.png
    dfad.png
    3.2 KB · Views: 74
  • #12
evinda said:
If the input is $000101010$ and the output this : $011001110$ the desired dfa is of the following form, right?

Yep. Looks like it! (Nod)
 
  • #13
I like Serena said:
Yep. Looks like it! (Nod)

Nice! (Smile)
 

FAQ: Designing a Deterministic Finite Automaton for Binary Input and Output Sequences

What is a deterministic machine?

A deterministic machine is a mathematical model that follows a specific set of rules and inputs to produce a predictable output. It operates on the principle of cause and effect, where the same input will always result in the same output.

How is a deterministic machine different from a non-deterministic machine?

A deterministic machine follows a single path of execution, while a non-deterministic machine can have multiple paths and may produce different outputs for the same input. This means that a deterministic machine is more predictable and reliable in its outputs.

What are some real-world examples of deterministic machines?

Some examples of deterministic machines include calculators, vending machines, and traffic lights. These machines follow a specific set of rules and inputs to produce a predictable output.

What role do algorithms play in deterministic machines?

Algorithms are the set of rules that dictate how a deterministic machine operates. They outline the specific steps and conditions for the machine to follow in order to produce the desired output.

How are deterministic machines used in scientific research?

Deterministic machines are used in scientific research as they provide reliable and predictable results. They can be used to model and simulate various natural phenomena, which can help scientists better understand and predict real-world events.

Similar threads

MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
Replies
1
Views
2K
Comp Sci Problem on undecidable problems
Replies
6
Views
2K
5-bit synchronous sequence recognizer design
Replies
17
Views
5K
Designing a Mealy State Machine for Input Sequences and Output Functions
Replies
18
Views
9K
Deterministic Finite State Automaton Construction
Replies
1
Views
2K
MHB Designing a Non-deterministic 2-Tape Turing Machine for a Specific Language
Replies
1
Views
2K
Is There a Flaw in this Turing Test Reasoning?
Replies
9
Views
2K
How Do You Design a Moore Machine for a Specific Output Sequence?
Replies
2
Views
6K
All about Unicode /programming with Unicode [tutorial]
Replies
4
Views
15K
Challenge Math Challenge - January 2020
2
Replies
64
Views
14K

Hot Threads

Recent Insights

Back
Top