1.

$DFA1 = \left(Q , \Sigma , \delta , q_0 , F \right)$

$Q = \{ q_0 , q_1 , q_2 , q_3 , q_4 , q_5 , q_6 , q_7 , q_8 , q_9 , q_{10} , q_{11} ,q_{12} , q_{13} , q_{14} , q_{15} , q_{16} , q_{17} , q_{18} \}$

$\Sigma = \{ -,0,1,2,3,4,5,6,7,8,9 \}$

$q_0 = q_0$

$F = \{q_{17}\}$

δ:

δ	0,1,...,9	-
--> $q_0 $	$q_1 $	$q_{18}$
$q_1 $	$q_2 $	$q_{18}$
$q_2 $	$q_3 $	$q_{18}$
$q_3 $	$q_{18}$	$q_4 $
$q_4 $	$q_5 $	$q_{18}$
$q_5 $	$q_{18}$	$q_6 $
$q_6 $	$q_7 $	$q_{18}$
$q_7 $	$q_8 $	$q_{18}$
$q_8 $	$q_{18}$	$q_9 $
$q_9 $	$q_{10}$	$q_{18}$
$q_{10}$	$q_{11}$	$q_{18}$
$q_{11}$	$q_{12}$	$q_{18}$
$q_{12}$	$q_{13}$	$q_{18}$
$q_{13}$	$q_{14}$	$q_{18}$
$q_{14}$	$q_{15}$	$q_{18}$
$q_{15}$	$q_{18}$	$q_{16}$
$q_{16}$	$q_{17}$	$q_{18}$
$* q_{17}$	$q_{18}$	$q_{18}$
$q_{18}$	$q_{18}$	$q_{18}$



In [4]:

    
class DFA:
    def __init__(self, estados, alfabeto, delta, inicial, finales):
        self.estados = set(estados)
        self.inicial = inicial
        self.delta = delta
        self.finales = set(finales)
        self.alfabeto = set(alfabeto)
        self.actual = inicial

    def EvaluaSimbolo(self, simbolo):
        self.actual = self.delta(self.actual, simbolo)

    def EvaluaSecuenciaValida(self, secuencia):
        for s in secuencia:
            self.EvaluaSimbolo(s)
        return (self.actual in self.finales)

def GetDFA_ISBN():
    estados = range(19)
    alfabeto = range(11)
    inicial = 0
    finales = {13}
    
    tt = {}
    for q in estados:
        tt[q] = {}
        for c in alfabeto:
            tt[q][c] = q+1 if q < 14 else q
    delta = lambda q, c: tt[q][c]
    
    return DFA(estados, alfabeto, delta, inicial, finales)


myDFA = GetDFA_ISBN()

ISBN = 3454332536452
ISBN2 = 3454332536-4521
secuencia = [int(i) for i in str(ISBN)]
secuencia2 = [int(i) for i in str(ISBN2)]
print("Valido!" if myDFA.EvaluaSecuenciaValida(secuencia) else "No valido.")
print("Valido!" if myDFA.EvaluaSecuenciaValida(secuencia2) else "No valido.")









    



Valido!
No valido.

2.

δ:

δ	a	b
-> * q0	q1	q4
* q1	q2	q4
* q2	q3	q4
q3	q3	q3
* q4	q1	q5
* q5	q1	q6
q6	q6	q6

$DFA2 = \left(Q~,~\Sigma~,~\delta~,~q_0~,~F \right)$

$Q = \{ q_0 , q_1 , q_2 , q_3 , q_4 , q_5 , q_6 \}$

$\Sigma = \{ a , b \}$

$q_0 = q_0$

$F = \{q_0 , q_1 , q_2 , q_4 , q_5\}$

3.

Teniendo el DFA $M$ definido tal que:
$M=\left(Q , \Sigma , \delta , q_0 , F\right)$.
Buscamos construir un DFA $M'$ definido como:
$M'=\left(Q , \Sigma , \delta , q_0 , F'\right)$ donde $F'= F^C \cap Q $.

Teniendo en cuenta que $u \in \Sigma^\ast $ se sigue que si: $u \in L(M)$
Entonces por definición de $\hat\delta()$ tenemos que
$\hat{\delta}\left(q_0,u\right)\in F$.
Y por lo tanto:
$\hat{\delta}(q_0,u)\notin F^C \cap Q \,\,\,\equiv\,\,\, \hat{\delta}(q_0,u)\notin F'$ en consecuencia $u \notin L(M')$.

Por otro lado, si $u \notin L(M)$
Entonces:
$\hat{\delta}\left(q_0,u\right)\notin F$.
Y por lo tanto:
$\hat{\delta}(q_0,u)\in F^C \cap Q \,\,\,\equiv\,\,\, \hat{\delta}(q_0,u)\in F'$ en consecuencia $u \in L(M')$.

Así tenemos que $u \in L(M)$ si y solo si $u \notin L(M')$.

5.

δ	1 1 1	2	3
$q_{0}$	$\{q_{1}\}$	$\{q_{2}\}$	$\{q_{3}\}$
$q_{1}$	$\{q_{1},q_{6}\}$	$\{q_{2}\}$	$\{q_{3}\}$
$q_{2}$	$\{q_{1},q_{2}\}$	$\{q_{2},q_{5}\}$	$\{q_{3}\}$
$q_{3}$	$\{q_{1},q_{3}\}$	$\{q_{2},q_{3}\}$	$\{q_{3},q_{4}\}$
$q_{4}$	$ \Phi $	$ \Phi $	$ \Phi $
$q_{5}$	$ \Phi $	$ \Phi $	$ \Phi $
$q_{6}$	$ \Phi $	$ \Phi $	$ \Phi $

1.

δ:

2.

δ:

3.

5.

6.