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

Tamaño de esta previsualización: 800 × 574 píxeles. Otras resoluciones: 320 × 229 píxeles · 640 × 459 píxeles · 1024 × 734 píxeles · 1166 × 836 píxeles.

Ver la imagen en su resolución original ‎(1166 × 836 píxeles; tamaño de archivo: 31 kB; tipo MIME: image/gif)

Resumen

Descripción	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.
Fecha	27 de noviembre de 2013, 15:51:16
Fuente	Trabajo propio
Autor	Jochen Burghardt

Esta imagen debería volverse a crear como imágenes vectoriales SVG. Esto proporciona muchas ventajas, véase Commons:Media for cleanup (en inglés) para más información. Si ya hay una versión SVG de esta imagen disponible, por favor súbala a Commons. Tras subirla, reemplace esta plantilla con la plantilla {{vector version available|nuevo nombre de imagen.svg}} en esta imagen.

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

Licencia

Yo, el titular de los derechos de autor de esta obra, la publico en los términos de la siguiente licencia:

Este archivo se encuentra bajo la licencia Creative Commons Genérica de Atribución/Compartir-Igual 3.0.

Eres libre:

de compartir – de copiar, distribuir y transmitir el trabajo
de remezclar – de adaptar el trabajo

Bajo las siguientes condiciones:

atribución – Debes otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si realizaste algún cambio. Puedes hacerlo de cualquier manera razonable pero no de manera que sugiera que el licenciante te respalda a ti o al uso que hagas del trabajo.
compartir igual – En caso de mezclar, transformar o modificar este trabajo, deberás distribuir el trabajo resultante bajo la misma licencia o una compatible como el original.

Historial del archivo

Haz clic sobre una fecha y hora para ver el archivo tal como apareció en ese momento.

	Fecha y hora	Dimensiones	Usuario	Comentario
actual	11:19 28 ago 2019	1166 × 836 (31 kB)	Jochen Burghardt	graph drawn with xgraph; negative-example regions drawn with gimp splines; regular expressions factorized
	19:07 3 feb 2016	1478 × 754 (27 kB)	Jochen Burghardt	fixed remaining counterexamples, after checking them with an sed script: even more automata recognize "0"
	13:06 2 feb 2016	1478 × 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 feb 2016	1478 × 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 nov 2013	1616 × 765 (29 kB)	Jochen Burghardt	User created page with UploadWizard