File:DFA example multiplies of 3.svg

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

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

Captions

Captions

Add a one-line explanation of what this file represents

Summary[edit]

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
Transition monoid
  ε
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[edit]

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.

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 Burghardt (talk | contribs)colorize state circles
18:31, 12 February 2018Thumbnail for version as of 18:31, 12 February 2018358 × 158 (8 KB)Leyth (talk | contribs)Reshaped the graph again.
18:27, 12 February 2018Thumbnail for version as of 18:27, 12 February 2018654 × 194 (8 KB)Leyth (talk | contribs)Enhancing 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)Mormegil (talk | contribs)bottom arrows fixed
03:08, 20 March 2007Thumbnail for version as of 03:08, 20 March 20071,230 × 523 (19 KB)Mikm (talk | contribs)Fixed two of the arrows
03:05, 20 March 2007Thumbnail for version as of 03:05, 20 March 20071,230 × 523 (19 KB)Mikm (talk | contribs){{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

You cannot overwrite this file.

File usage on other wikis

Metadata

This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.

Retrieved from "https://commons.wikimedia.org/w/index.php?title=File:DFA_example_multiplies_of_3.svg&oldid=646839620"