Jump to content

File:DFA example multiplies of 3.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (SVG file, nominally 358 × 158 pixels, file size: 7 KB)

Summary

Description
English: Example of a DFA that accepts binary numbers that are multiples of 3.
Čeština: Příklad deterministického konečného automatu, který přijímá binární čísla, která jsou beze zbytku dělitelná třemi.
Date
Source Own work
Author Self-made
Other versions Original PNG
  ε
012		 0
021		 1
102		 10
120		 01
201		 010
210
ε
012 		ε
012		 0
021		 1
102		 10
120		 01
201		 010
210
0
021 		0
021		 ε
012		 01
201		 010
210		 1
102		 10
120
1
102 		1
102		 10
120		 ε
012		 0
021		 010
210		 01
201
10
120 		10
120		 1
102		 010
210		 01
201		 ε
012		 0
021
01
201 		01
201		 010
210		 0
021		 ε
012		 10
120		 1
102
010
210 		010
210		 01
201		 10
120		 1
102		 0
021		 ε
012

Numeric entries denote functions mapping a state to a state; e.g. 102 abbreviates the function mapping state 0, 1, and 2 to state 1, 0, and 2, respectively; this is the function for digesting an input "1". The table shows the result of function composition, e.g. 021 ∘ 102 = 201, and 102 ∘ 021 = 120. Grey entries give a shortest input string corresponding to a function.

Equivalent alternate representations
Regular grammar
(Start symbol S0):
S0 → ε | 0 S0 | 1 S1
S1 → 0 S2 | 1 S0
S2 → 0 S1 | 1 S2

Regular expression:

(0|(1(01*(00)*0)*1)*)*

Licensing

Public domain I, the copyright holder of this work, release this work into the public domain. This applies worldwide.
In some countries this may not be legally possible; if so:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

inception

20 March 2007

media type

image/svg+xml

checksum

9fd8169865e66c0aabac0fd077b62a9e4e42bc14

determination method or standard: SHA-1

data size

7,258 byte

height

158 pixel

width

358 pixel

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current08:38, 4 November 2020Thumbnail for version as of 08:38, 4 November 2020358 × 158 (7 KB)Jochen Burghardtcolorize state circles
18:31, 12 February 2018Thumbnail for version as of 18:31, 12 February 2018358 × 158 (8 KB)LeythReshaped the graph again.
18:27, 12 February 2018Thumbnail for version as of 18:27, 12 February 2018654 × 194 (8 KB)LeythEnhancing the graph with an automata generation helper.
16:33, 16 May 2008Thumbnail for version as of 16:33, 16 May 20081,230 × 523 (21 KB)Mormegilbottom arrows fixed
03:08, 20 March 2007Thumbnail for version as of 03:08, 20 March 20071,230 × 523 (19 KB)MikmFixed two of the arrows
03:05, 20 March 2007Thumbnail for version as of 03:05, 20 March 20071,230 × 523 (19 KB)Mikm{{Information |Description= (en) Example of a DFA that accepts binary numbers that are multiplies of 3. (cs) Ukázka deterministického konečného automatu, který přijímá binární čísla, která jsou beze zbytku dělitelná třemi. |Source= Self-m

Global file usage

Metadata

This file contains additional information, probably added from the digital camera or scanner used to create or digitize it.

If the file has been modified from its original state, some details may not fully reflect the modified file.

Retrieved from "https://en.wikipedia.org/wiki/File:DFA_example_multiplies_of_3.svg"