import java.io.*;
class Defautomate_det {
    int Etat[][];
    int NbEtat[];
    int NumEtat;
    int Table[][][];
    int NSucc[][];
    int Initial[];
    int Final[];
    int MaxF;
    int MaxI;
    int SupEtat;
    public String Vocab = "abcdefghijklmnopqrstuvwxyz";
    Defautomate_det(int N)
    {
	Table = new int[N][N][26];
	NSucc = new int[N][26];
	Final = new int[N];
	Initial = new int[N];
	Etat = new int[2][N];
	NbEtat = new int[2];
	SupEtat = N;
	MaxF = 0;
	MaxI = 0;
	for(int I = 0; I < N; ++I)
	    for(int J = 0; J < N; ++J)
		for(int K = 0; K < 26; ++K)
		    Table[I][J][K] = -1;
	for(int I = 0; I < N; ++I)
	    for(int J = 0; J < 26; ++J)
		NSucc[I][J] = 0;
    }
    boolean Ecriture_Transition(int Q,int Symbole,int QR)
    {
	if ((Q < 0) || (Q >= SupEtat) || (Symbole < 0) || (Symbole >= 26) |
	    (QR < 0) || (QR >= SupEtat) || (NSucc[Q][Symbole] >= SupEtat))
	return false;
	Table[Q][NSucc[Q][Symbole]++][Symbole] = QR;
	return true;
    }
    boolean Ecriture_Finale(int F)
    {
	if ((F >= SupEtat) || (MaxF >= SupEtat))
	    return false;
	Final[MaxF++] = F;
	return true;
    }
    boolean Ecriture_Initiale(int I)
    {
	if ((I >= SupEtat) || (MaxI >= SupEtat))
	    return false;
	Initial[MaxI++] = I;
	return true;

    }
    boolean Transition(int V)
    {
	int c = Vocab.indexOf(V);
	if ((c < 0) || (c >= 26) || (NbEtat[NumEtat] <= 0))
	{
	    NbEtat[NumEtat] = 0;
	    return false;
	}
	int EtatSuiv = (NumEtat + 1) % 2;
	NbEtat[EtatSuiv] = 0;
	for(int i = 0; i < NbEtat[NumEtat]; ++i)
	    for(int k = 0; k < NSucc[Etat[NumEtat][i]][c]; ++k)
	    {
		int l;
		for(l = 0; l < NbEtat[EtatSuiv]; ++l)
		    if (Etat[EtatSuiv][l] == Table[Etat[NumEtat][i]][k][c])
			break;
		if (l == NbEtat[EtatSuiv])
		    Etat[EtatSuiv][NbEtat[EtatSuiv]++] = Table[Etat[NumEtat][i]][k][c];
	    }
	NumEtat = EtatSuiv;
	if (NbEtat[NumEtat] <= 0)
	    return false;
	return true;
    }
    boolean Resultat()
    {
	for(int I = 0; I < NbEtat[NumEtat]; ++I)
	    for(int J = 0; J < MaxF; ++J)
		if (Final[J] == Etat[NumEtat][I])
		    return true;
	return(false);
    }
    void Depart()
    {
	for(int I = 0; I < MaxI; ++I)
	    Etat[0][I] = Initial[I];
	NbEtat[0] = MaxI;
	NumEtat = 0;
	return;
    }
    void SortieAutomate()
    {
	int Pile[][] = new int[256][SupEtat];
	int NbElemPile[] = new int[256];
	int NouvTrans[][] = new int[256][26];
	int IdentEtat[] = new int[SupEtat];
	int Ipile;
	int IcourPile;
	int ValIdent;
	ValIdent = 0;
	for(int I = 0; I < MaxI; ++I)
		Pile[0][I] = Initial[I];
	Ipile = 1;
	IcourPile = 0;
	NbElemPile[IcourPile] = MaxI;
	while(IcourPile < Ipile)
	{
	    int J;
	    for(int I = 0; I < 26; ++I)
	    {
		ValIdent = 0;
		for(J = 0; J < NbElemPile[IcourPile]; ++J)
		    for(int K = 0; K < NSucc[Pile[IcourPile][J]][I]; ++K)
		    {
			int L;
			for(L = 0; L < ValIdent; ++L)
			    if (IdentEtat[L] == Table[Pile[IcourPile][J]][K][I])
				break;
			if (L == ValIdent)
			    place(IdentEtat,ValIdent++,Table[Pile[IcourPile][J]][K][I]);
		    }
		if (ValIdent != 0)
		{
		    for(J = 0; J < Ipile; ++J)
		    {
		        if (ValIdent == NbElemPile[J])
		        {
			    int K;
		            for(K = 0; K < ValIdent; ++K)
			        if (Pile[J][K] != IdentEtat[K])
			            break;
		            if (K == ValIdent)
			        break;
		        }
		    }
	            if (J == Ipile)
	            {
		        for(int K = 0; K < ValIdent; ++K)
			    Pile[Ipile][K] = IdentEtat[K];
		        NbElemPile[Ipile] = ValIdent;
		        ++Ipile;
	            }
	            NouvTrans[IcourPile][I] = J;
		}
		else NouvTrans[IcourPile][I] = -1;
	    }
	    ++IcourPile;
	}
	System.out.println("Sortie automate:");
	System.out.println("Nombre d'etats: " + Ipile);
	System.out.print("Etats finals: ");
	boolean D = true;
        for(IcourPile = 0; IcourPile < Ipile; ++IcourPile)
	    for(int I = 0; I < NbElemPile[IcourPile]; ++I)
	    {
		int J;
		for(J = 0; J < MaxF; ++J)
		    if (Pile[IcourPile][I] == Final[J])
			break;
		if (J != MaxF)
		{
		    if (D)
		    {
			System.out.print(IcourPile);
			D = false;
		    }
		    else System.out.print("," + IcourPile);
		    break;
		}
	    }
	System.out.println("");
	System.out.println("Fonction de transition:");
	for(IcourPile = 0; IcourPile < Ipile; ++IcourPile)
	    for(int I = 0; I < 26; ++I)
		if (NouvTrans[IcourPile][I] != -1)
			System.out.println("(" + IcourPile + "," + Vocab.charAt(I) + ")->" + NouvTrans[IcourPile][I]);

    }
    void place(int Ident[],int Nelem,int Npla)
    {
	int I;
	for(I = 0; I < Nelem; ++I)
	    if (Ident[I] > Npla)
		break;
	for(int J = Nelem - 1; J >= I; --J)
		Ident[J + 1] = Ident[J];
	Ident[I] = Npla;
    }
}
class automatedet {
public static void main(String args[]) {
try {
    if (args.length != 1)
    {
	System.out.println("Pas de parametre d'appel: <Nom du fichier de definition>");
	return;
    }
    DataInput d = new DataInputStream(new FileInputStream(args[0]));
    String entree;
    if((entree = d.readLine()) == null)
    {
	System.out.println("fichier de definition vide");
	return;
    }
    if (!entree.startsWith("Nombre d'etats: "))
    {
	System.out.println("La definition de l'automate doit commencer par:");
	System.out.println("Nombre d'etats: ");
	return;
    }
    int p = entree.indexOf(':') + 2;
    int N = Integer.parseInt(entree.substring(p));
    Defautomate_det A = new Defautomate_det(N);
    if((entree = d.readLine()) == null)
    {
	System.out.println("fichier de definition incomplet");
	return;
    }
    if (!entree.startsWith("Etats initiaux: "))
    {
	System.out.println("La definition de l'automate doit comprendre:");
	System.out.println("Etats initiaux: ");
	return;
    }
    p = entree.indexOf(':') + 2;
    int v,f;
    while((f = entree.indexOf(',',p)) > 0)
    {
	try {
	    v = Integer.parseInt(entree.substring(p,f));
	} catch (NumberFormatException e)
	{
	    System.out.println("Definition d'un etat initial incorrecte:");
	    return;
	}
	if (!A.Ecriture_Initiale(v))
	{
	    System.out.println("Definition de l'etat initial incorrecte: " + v);
	    return;
	}
	p = f + 1;
    }
    try {
	v = Integer.parseInt(entree.substring(p));
    } catch (NumberFormatException e)
    {
	System.out.println("Definition du dernier etat initial incorrecte:");
	return;
    }
    if (!A.Ecriture_Initiale(v))
    {
	System.out.println("Definition de l'etat initial incorrecte: " + v);
	return;
    }
    if((entree = d.readLine()) == null)
    {
	System.out.println("fichier de definition incomplet");
	return;
    }
    if (!entree.startsWith("Etats finals: "))
    {
	System.out.println("La definition de l'automate doit comprendre:");
	System.out.println("Etats finals: ");
	return;
    }
    p = entree.indexOf(':') + 2;
    while((f = entree.indexOf(',',p)) > 0)
    {
	try {
	    v = Integer.parseInt(entree.substring(p,f));
	} catch (NumberFormatException e)
	{
	    System.out.println("Definition d'un etat final incorrecte:");
	    return;
	}
	if (!A.Ecriture_Finale(v))
	{
	    System.out.println("Definition de l'etat final incorrecte: " + v);
	    return;
	}
	p = f + 1;
    }
    try {
	v = Integer.parseInt(entree.substring(p));
    } catch (NumberFormatException e)
    {
	System.out.println("Definition du dernier etat final incorrecte:");
	return;
    }
    if (!A.Ecriture_Finale(v))
    {
	System.out.println("Definition de l'etat final incorrecte: " + v);
	return;
    }
    if((entree = d.readLine()) == null)
    {
	System.out.println("fichier de definition incomplet");
	return;
    }
    if (!entree.equals("Fonction de transition:"))
    {
	System.out.println("La definition de l'automate doit comprendre:");
	System.out.println("Fonction de transition:");
	return;
    }
    while((entree = d.readLine()) != null)
    {
	p = entree.indexOf('(') + 1;
	f = entree.indexOf(',');
	try {
	    v = Integer.parseInt(entree.substring(p,f));
	} catch (NumberFormatException e)
	{
	    System.out.println("Definition de l'etat d'une transition incorrecte: " + entree.substring(p,f));
	    return;
	}
	p = f + 1;
	f = entree.indexOf(')');
	String prov = entree.substring(p,f);
	int c;
	if ((prov.length() != 1) || ((c = A.Vocab.indexOf(prov)) < 0))
	{
	    System.out.println("Definition du caractere d'une transition incorrecte: " + prov);
	    return;
	}
	p = entree.indexOf("->") + 2;
	int r;
	try {
	    r = Integer.parseInt(entree.substring(p));
	} catch (NumberFormatException e)
	{
	    System.out.println("Definition de l'etat resultant d'une transition incorrecte: " + entree.substring(p));
	    return;
	}
	if (!A.Ecriture_Transition(v,c,r))
	{
	    System.out.println("Definition d'une transition incorrecte ou dupliquee: " + entree);
	    return;
	}
    }
    while(true) {
	System.out.print("Entrez un mot (ligne vide pour arreter): ");
	try {
	    v = System.in.read();
	} catch (IOException e)
	{
	    System.out.println("Erreur de lecture");
	    return;
	}
	if (v == '\n')
	    break;
	A.Depart();
	boolean Ok = true;
	do {
	    if (Ok)
		Ok = A.Transition(v);
	    try {
		v = System.in.read();
	    } catch (IOException e)
	    {
		System.out.println("Erreur de lecture");
		return;
	    }
	} while(v != '\n');
	System.out.println("La chaine appartient au langage: " + (Ok && A.Resultat()));
    }
    A.SortieAutomate();
    return;
} catch (FileNotFoundException e) {
return ;
} catch (IOException e)
{
return ;
} catch (NullPointerException e)
{
return ;
}
}
}