Designing a Deterministic Finite Automaton for Binary Input and Output Sequences

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Machine
Click For Summary

Discussion Overview

The discussion revolves around designing a deterministic finite automaton (DFA) for a given binary input and output sequence. Participants explore the structure of the DFA, including the number of states and the transitions based on the input-output pairs. The focus is on theoretical aspects of automaton design, including potential typos in the output sequence and the implications for state reduction.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • Some participants suggest that the output sequence contains a typo, proposing to ignore the last digit to match the input length.
  • One participant proposes a state diagram for the DFA based on the assumption of a typo and no restrictions on the number of states.
  • There is a discussion about whether the DFA can be simplified by collapsing states B, C, D, and E into a single state due to identical transitions.
  • Another participant questions the necessity of final states in the presence of outputs, suggesting that they may not be required.
  • Concerns are raised about the implications of collapsing states, particularly regarding potential conflicts in transitions.
  • Participants explore the possibility of further collapsing states and the effects this may have on the state machine's functionality.

Areas of Agreement / Disagreement

Participants express differing views on the presence of typos in the output sequence and the necessity of final states. There is no consensus on the best approach to collapsing states, with some participants supporting the idea while others express confusion or concern about potential conflicts.

Contextual Notes

The discussion includes assumptions about the output sequence and the structure of the DFA that may not be universally accepted. The implications of state reduction and the necessity of final states remain unresolved.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
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
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)
 
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: 123
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)
 
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)
 
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)
 
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)
 
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)
 
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: 148
  • #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: 118
  • #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)
 

Similar threads

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