File:Thompson's construction algorithm applied to regular expression for binary multiples of 3.gif
From Wikimedia Commons, the free media repository
Jump to navigation
Jump to search
Size of this preview: 800 × 493 pixels. Other resolutions: 320 × 197 pixels | 640 × 394 pixels | 1,235 × 761 pixels.
Original file (1,235 × 761 pixels, file size: 9 KB, MIME type: image/gif)
File information
Structured data
Captions
Summary[edit]
DescriptionThompson's construction algorithm applied to regular expression for binary multiples of 3.gif |
English: Thompson's construction algorithm applied to the regular expression (0|(1(01*(00)*0)*1)*)* that denotes the set of binary numbers that are multiples of 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }. The upper right part shows the logical structure (syntax tree) of the expression, with "." denoting concatenation (assumed to have variable arity); subexpressions are named a-q for reference purposes. The left part shows the nondeterministic finite automaton resulting from Thompson's algorithm, with the entry and exit state of each subexpression colored in magenta and cyan, respectively. The entry and exit state corresponding to the root expression q is the start and accept state of the automaton, respectively. A simpler regular expression for the same set is (0|(1(01*0)*1))* . |
Date | |
Source | Own work |
Author | Jochen Burghardt |
This diagram image could be re-created using vector graphics as an SVG file. This has several advantages; see Commons:Media for cleanup for more information. If an SVG form of this image is available, please upload it and afterwards replace this template with
{{vector version available|new image name}} .
It is recommended to name the SVG file “Thompson's construction algorithm applied to regular expression for binary multiples of 3.svg”—then the template Vector version available (or Vva) does not need the new image name parameter. |
Licensing[edit]
I, the copyright holder of this work, hereby publish it under the following license:
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
- You are free:
- to share – to copy, distribute and transmit the work
- to remix – to adapt the work
- Under the following conditions:
- attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 23:04, 30 May 2014 | 1,235 × 761 (9 KB) | Jochen Burghardt (talk | contribs) | User created page with UploadWizard |
You cannot overwrite this file.
File usage on Commons
There are no pages that use this file.
File usage on other wikis
The following other wikis use this file:
- Usage on ar.wikipedia.org
- Usage on en.wikipedia.org
- Usage on fa.wikipedia.org
- Usage on pt.wikipedia.org
- Usage on ro.wikipedia.org