File:Thompson's construction algorithm applied to regular expression for binary multiples of 3.gif

Summary

Description
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.
Category:Diagram images that should use vector graphics#%20Thompson's%20construction%20algorithm%20applied%20to%20regular%20expression%20for%20binary%20multiples%20of%203.gifCategory:GIF that should be converted to SVG

Licensing

I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution share alike
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.
Category:CC-BY-SA-3.0#Thompson's%20construction%20algorithm%20applied%20to%20regular%20expression%20for%20binary%20multiples%20of%203.gifCategory:Self-published work
Category:Files by User:Jochen Burghardt Category:Regex Category:Thompson's construction (formal language theory)
Category:CC-BY-SA-3.0 Category:Diagram images that should use vector graphics Category:Files by User:Jochen Burghardt Category:GIF that should be converted to SVG Category:Pages with syntax highlighting errors Category:Regex Category:Self-published work Category:Thompson's construction (formal language theory)