File:Lattice of automata accepting 1, 10, and 100.gif

Size of this preview: 800 × 574 pixels. Other resolutions: 320 × 229 pixels | 640 × 459 pixels | 1,024 × 734 pixels | 1,166 × 836 pixels.

Original file ‎(1,166 × 836 pixels, file size: 31 KB, MIME type: image/gif)

This is a file from the Wikimedia Commons. Information from its description page there is shown below.
Commons is a freely licensed media file repository. You can help.

Summary

Description	English: Shows the partially ordered set of automata accepting the strings 1, 10, and 100 (positive examples). Each automaton is obtained by factoring the trivial undergeneralization (bottom node; there also sketched as automaton) with respect to the equivalence shown on light red background, and is denoted as an equivalent regular expression (on light green background). For each of the negative examples 11, 1001, 101, and 0, the upper set of automata accepting it is shown. For the leftmost branch, automaton images are available at File:Quotient automaton a,b,c,d.gif (1+10+100), File:Quotient automaton a=b,c,d.gif (1^(ε+0+00)), File:Quotient automaton a=b,c=d.gif (1^0^), and File:Quotient automaton a=b=c=d.gif ((0+1)^). According to Dupont et al., 1994 the automata form a lattice. This is true when two automata are considered equal iff they are obtained as quotient by the same equivalence, the lattice being trivially isomorphic to that of all state set partitions (see e.g. File:Lattice of partitions of an order 4 set.svg). However, it is false when two automata are considered equal iff they accept the same language, as the current picture shows: the a=b and the b=c=d automaton have two upper bounds, viz. the a=b,c=d and the a=b=d automaton, but no least one. For those automata pairs that do have a join or meet, these operations needn't coincide with language union or intersection, respectively. For example, the string 1101 is neither accepted by the a=b=d nor by the a=c=d automaton, while their join, a=b=c=d accepts it. Dually, the empty string is accepted by both the a=b and the a=d automaton, but not by their meet a,b,c,d.
Date	27 November 2013, 15:51:16
Source	Own work
Author	Jochen Burghardt

This computer science 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 “Lattice of automata accepting 1, 10, and 100.svg”—then the template Vector version available (or Vva) does not need the new image name parameter.

Shell script to check language memberships of counter-examples

#!/bin/sh
# For each of the 11 regular expressions obtained from factoring the
# automaton for "1|10|100" in all possible ways, check which of the
# counter-example strings it accepts.
# An accepted string is replaced by the automaton name in the output.
# (Automata are named by the factoring equivalence relation on
# the state set {a,b,c,d}).

for  a in                                                       \
        's/+ \(1\|10\|100\) +/+ a,b,c,d +/'                     \
        's/+ \(1*\|1*0\|1*00\) +/+ a=b +/'                      \
        's/+ \(1*0*\) +/+ a=b,c=d +/'                           \   
        's/+ \(\(0\|1\)*\) +/+ a=b=c=d +/'                      \
        's/+ \(\(100\)*\|\(100\)*1\|\(100\)*10\) +/+ a=d +/'    \
        's/+ \(\(1\|00\)*\|\(1\|00\)*0\) +/+ a=b=d +/'          \
        's/+ \(\(10*0\)*\|\(10*0\)*1\) +/+ a=d,b=c +/'          \
        's/+ \(10*\) +/+ b=c=d +/'                              \
        's/+ \(\(0\|10\)*\|\(0\|10\)*1\) +/+ a=c=d +/'          \   
        's/+ \(\(10\)*\|\(10\)*1\|\(10\)*0\) +/+ a=c +/'        \   
        's/+ \(\(00\|10\)*\|\(00\|10\)*\(0\|1\)\) +/+ a=c,b=d +/'
do

    # optical separator:
    echo "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"

    # somewhat beautified regular expression, and automaton name:
    echo "$a" | sed '
                s,\\,,g
                s,\*,",g
                s,s/+ (,,
                s,) +/+ ,\t\t,
                s,+/$,,
                '

    # result of applying the reg.exp. to the counter-example strings:
    sed -e "$a" <<EOF
                + 11 + 11 +
                + 1001 + 1001 +
                + 101 + 101 +
                + 0 + 0 +
EOF

done

Licensing

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	Dimensions	User	Comment
current	11:19, 28 August 2019	1,166 × 836 (31 KB)	Jochen Burghardt	graph drawn with xgraph; negative-example regions drawn with gimp splines; regular expressions factorized
	19:07, 3 February 2016	1,478 × 754 (27 KB)	Jochen Burghardt	fixed remaining counterexamples, after checking them with an sed script: even more automata recognize "0"
	13:06, 2 February 2016	1,478 × 754 (27 KB)	Jochen Burghardt	fixed counterexample: (''a''=''c'') also accepts "0", since the 3rd summand of its reg.exp., (10)*0, does
	12:43, 2 February 2016	1,478 × 754 (26 KB)	Jochen Burghardt	fixed incorrect order relations, e.g. 10<sup></sup> ⊆ 1<sup></sup>0<sup>*</sup>, corresponding to (''c''=''d'') ← (''a''=''b'',''c''=''d''), was missing
	15:08, 27 November 2013	1,616 × 765 (29 KB)	Jochen Burghardt	User created page with UploadWizard