P-FLAT --- Prolog toolkit for Formal Languages and Automata Theory

Artur Miguel Dias

Última modificação: 21/Mar/2006
Enviar comentários e correcções para amd@di.fct.unl.pt

Changelog

21/MAR/2006 Foi corrigido um erro na expressão regular usada nos primeiros exemplos, nesta página.
10/MAR/2006 Primeira versão deste documento.

Apresentação

O P-FLAT consiste numa implementação pedagógica duma parte substancial dos conceitos estudados em LFA. Está escrito em Prolog, sendo o código da implementação bastante fiel às definições apresentadas na cadeira.

Interactua-se com o sistema através a linha de comandos do Prolog ou usando scripts escritos em Prolog.

As entidades suportadas pelo programa são as seguintes:

Conjuntos
Símbolos e alfabetos
Palavras
Linguagens (podem ser parcialmente especificadas usando testes unitários)
Predicados (um predicado P define a linguagem {w: P(w)})
Expressões regulares
Autómatos finitos
Gramáticas independentes do contexto
Autómatos de pilha
Máquinas de Turing

Há três níveis de utilização do P-FLAT:

Nível 1 - O aluno encara o P-FLAT como fornecendo um conjunto de comandos que se destinam a ser rigidamente usados, um de cada vez. Usa assim os comandos individualmente para fazer experiências com os conceitos da cadeira e confirmar os resultados da resolução de alguns exercícios. Neste nível, o aluno precisa apenas de conhecer a funcionalidade dos comandos, não necessitando de estudar a sua implementação.
Nível 2 - O aluno encara o P-FLAT como uma biblioteca de predicados Prolog e usa-os para efectuar queries compostas e para programar mais predicados. Tal como no nível anterior, o aluno continua a tirar partido da funcionalidade das operações disponíveis (embora de forma mais sofisticada) sem necessitar de estudar a sua implementação.
Nível 3 - O aluno extende o sistema, introduzindo nova funcionalidade fundamental.

O P-FLAT está sendo desenvolvido por Michel Wermelinger e Artur Miguel Dias. A ideia original foi de Michel Wermelinger. Eis um curto artigo onde se apresenta o sistema de forma introdutória.

Activação

Para correr o P-FLAT no Linux, use o comando "pl -s pflat.pl". No Windows basta clicar no ícone do ficheiro "pflat.pl".

Uso através da linha de comando

Efectuemos algumas experiências simples usando a expressão regular (0 + 1 0^* 1)^*, que descreve a linguagem das sequências binárias onde o símbolo "1" ocorre um número par de vezes. No que se segue, o input do utilizador aparece a vermelho. Repare também que a expressão regular teve de ser escrita usando sintaxe modificada, para poder ser lida pelo Prolog.

> pl -s pflat.pl
% pflat.pl compiled 0.06 sec, 124,668 bytes
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.7)
Copyright (c) 1990-2006 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).


?- show((0 + 1 * 0^* * 1)^*).            % Mostra a expressão regular
REGULAR EXPRESSION:
  Definition: re((0+1*0^* *1)^*)
Yes

?- alpha((0 + 1 * 0^* * 1)^*, X).        % Pede o alfabeto da expressão regular
X = {1, 0}
Yes

?- accept((0 + 1 * 0^* * 1)^*, [1,1]).   % Pergunta se a palavra "11" pertence à linguagem definida pela expressão regular
Yes

?- accept((0 + 1 * 0^* * 1)^*, [1,0]).   % Pergunta se a palavra "10" pertence à linguagem definida pela expressão regular
No

?- word((0 + 1 * 0^* * 1)^*, X).         % Gera algumas palavras para verificar empiricamente se a expressão define mesmo a linguagem pretendida
X = [] ;
X = [0] ;
X = [0, 0] ;
X = [1, 1] ;
X = [0, 0, 0] ;
X = [1, 1, 0] ;
X = [1, 0, 1] ;
X = [0, 1, 1] ;
X = [0, 0, 0, 0] ;
X = [1, 1, 0, 0] ;
X = [1, 0, 1, 0] ;
X = [0, 1, 1, 0] ;
X = [1, 0, 0, 1] ;
X = [0, 1, 0, 1] ;
X = [0, 0, 1, 1] ;
X = [1, 1, 1, 1] ;
X = [0, 0, 0, 0, 0] ;
X = [1, 1, 0, 0, 0]
Yes

?- tracing((0 + 1 * 0^* * 1)^*, [1,1]).  % Pede a prova detalhada de que a palavra "11" pode ser obtida a partir da expressão regular
TRACING REGULAR EXPRESSION:
  Traced word: [1, 1]
  At least one execution path stops at an acceptance state. Word accepted.
  Traced steps:
    >1 1    ((0+1*0^* *1)^*)
    >1 1    (0+1*0^* *1) ((0+1*0^* *1)^*)
    >1 1    (1*0^* *1) ((0+1*0^* *1)^*)
    >1 1    (1*0^*) (1) ((0+1*0^* *1)^*)
    >1 1    (1) (0^*) (1) ((0+1*0^* *1)^*)
     1>1    1 (0^*) (1) ((0+1*0^* *1)^*)
     1>1    1 (1) ((0+1*0^* *1)^*)
     1 1>   1 1 ((0+1*0^* *1)^*)
     1 1>   1 1
Yes

?-

Eis a documentação dos predicados usados nesta secção, copiada directamente do ficheiro fonte do P-FLAT:

/*
alpha(?E,-A)                  The alphabet of entity E is A
show(?E)                      Display entity E
accept(?E, +W)                E accepts W
accept(?E, +W, -Path)         E accepts W with execution path Path
word(?E, -W)                  E generates W (results are ordered)
tracing(+E, +W)               Trace E accepting W
*/

Para ter uma ideia das outras habilidades do P-FLAT, veja a secção "Predicados disponíveis", perto do final deste documento.

Escrita de scripts

Apesar de ser possível usar o P-FLAT da forma exemplificada na secção anterior, trabalhando directamente sobre a linha de comando, muitas vezes é melhor registar em ficheiro as declarações e os comandos que nos interessam e depois consultar esse ficheiro. Cria-se assim um script prático de usar e que pode ser guardado para o futuro.

A escrita de um script pode revelar-se um pouco trabalhosa se se pretender produzir output elaborado. Para ajudar, o P-FLAT disponibiliza os predicados execute/1 e execute/3 que sabem executar comandos, gerando automaticamente output razoavelmente expressivo.

Para exemplificar, eis um script contendo uma declaração e diversos comandos:

re(evenRE, (0 + 1 * 0^* * 1)^*).                % Declara expressão regular
:- execute(show(evenRE)).                       % Mostra a expressão regular
:- execute(alpha(evenRE,A), A, true).           % Pede o alfabeto da expressão regular
:- execute(accept(evenRE, [1,1])).              % Pergunta se a palavra "11" pertence à linguagem definida pela expressão regular
:- execute(accept(evenRE, [0,1])).              % Pergunta se a palavra "10" pertence à linguagem definida pela expressão regular
:- execute(word(evenRE,A), A, length(A,4)).     % Gera palavras até aparecer a primeira com comprimento 4
:- execute(tracing(evenRE, [1,1])).             % Pede a prova detalhada de que a palavra "11" pode ser obtida a partir da expressão regular

Para consultar o ficheiro "fich.pl", você faz:

[fich].

Neste caso, o output produzido é quase igual ao da secção anterior.

Os ficheiros "tutorial.pl" e "examples.pl" fazem parte da distribuição do P-FLAT. São scripts que ilustram diversos aspectos da utilização do P-FLAT.

Eis a documentação dos predicados execute/1 e execute/3, copiada directamente do ficheiro fonte do P-FLAT:

/*
execute(+G, ?R, +S)     Call goal G and write result R until G fails or stop condition S succeeds
execute(+G)             Call goal G and print 'Yes' ou 'No'
*/

Declarações

O P-FLAT permite declarar entidades em ficheiro, associando um nome a cada uma delas. Por exemplo, é desta forma que se declara uma expressão regular chamada evenRE.

re(evenRE, (0 + 1 * 0^* * 1)^*).

Apresentam-se agora diversas declarações para ilustrar todo o tipo de entidades declaráveis em P-FLAT (existem nove tipos ao todo):

% alfabeto
alphabet(bitsA, {0,1}).

% relação de ordem total
alphabet_order(upO, bitsA, [0,1]).               % relação de ordem total sobre o alfabeto bitsA
alphabet_order(upO, {0,1}, [0,1]).               % também se pode declarar assim.
alphabet_order(downO, bitsA, [1,0]).             % outra relação de ordem total sobre o alfabeto bitsA

% linguagem
language(evenL, bitsA).                          % linguagem sobre o alfabeto bitsA
language(evenL, {0,1}).                          % também se pode declarar assim...
language(evenL, {0}+{1}).                        % ...ou assim.

% predicado
predicate(evenP, bitsA).                         % define a linguagem {w: evenP(w)}

% expressão regular
re(evenRE, (0 + 1 * 0^* * 1)^*).

% autómato finito
fa(abFA,
   1,                      % estado inicial
   {1/a/1, 1/a/2, 1/b/2,   % transições
    2/b/2, 2/b/1
   },
   {2}                     % estados finais
  ).

% gramática independente do contexto
cfg(arithCFG,
    'E',                   % símbolo de partida
    {('E'->['E',+,'T']),   % produções
     ('E'->['T']),
     ('T'->['T',*,'F']),
     ('T'->['F']),
     ('F'->['(','E',')']),
     ('F'->[a])
    }
   ).

% autómato de pilha
pda(mirrorPDA,
    i,                      % estado inicial
    z,                      % símbolo inicial da pilha
    {i/z/[]/i/[z], i/z/a/p/[a,z], i/z/b/p/[b,z], % transições
     p/a/a/p/[a,a], p/a/b/p/[b,a],
     p/b/a/p/[a,b], p/b/b/p/[b,b],
     p/a/a/q/[], p/b/b/q/[],
     q/a/a/q/[], q/b/b/q/[],
     q/z/[]/t/[z]
    },
    {i,t}                   % estados finais
   ).

% máquina de Turing
tm(swapabTM,
   q0,                      % estado inicial
   {q0/'B'/'B'/'R'/q0, q0/a/a/'L'/q0,    q0/'B'/'B'/'R'/q1, % transições
    q1/a/b/'R'/q1,     q1/b/a/'R'/q1,    q1/'B'/'B'/'L'/q2,
    q2/a/a/'L'/q2,     q2/b/b/'L'/q2,    q2/'B'/'B'/'R'/q3
   },
   {q3}                     % estados finais
  ).

Declaração de linguagens e de predicados

No P-FLAT, quase todos os tipos de declarações são auto-suficientes, no sentido em que a própria declaração já inclui toda a informação necessária para caracterizar a entidade em causa. Há duas excepções: as declarações de linguagens e as declarações de predicados.

Declaração de linguagens

Deve complementar-se a declaração duma linguagem com um conjunto de factos Prolog que exemplificam palavras que pertencem à linguagem e palavras que não pertencem à linguagem. Chama-se a esse factos testes unitários. Os testes unitários têm a forma

in_language(Word, Name, Boolean)

e afirmam que a palavra Word pertence ou não à linguagem Name, consoante o valor de Boolean.

Para exemplificar, eis uma declaração mais completa da linguagem evenL:

language(evenL, {0,1}).

in_language([], evenL, true).
in_language([0,0,0], evenL, true).
in_language([1,1], evenL, true).
in_language([0,1,1], evenL, true).
in_language([1,1,0,0], evenL, true).
in_language([1,0,0,0,1,1,0,1], evenL, true).
in_language([1], evenL, false).
in_language([1,1,1], evenL, false).
in_language([1,0,0], evenL, false).
in_language([0,0,1], evenL, false).
in_language([1,0,0,1,1,0,0], evenL, false).

Recomendamos que você defina sempre pelos menos 5 casos positivos e cinco casos negativos, tendo ainda o cuidado de identificar as situações limite mais importantes.

A importância dos testes unitários

Imagine que você tem em mente uma determinada linguagem e pretende representá-la usando uma das técnicas estudadas em LFA, digamos usando um autómato finito. Nesse caso, deve declarar primeiro a linguagem e associar-lhe um conjunto de testes unitários. Só depois é que deve tentar escrever o autómato. Vale a pena o primeiro passo pelas seguintes razões:

Em resultado do esforço de escrever os testes unitários, você fica com uma ideia mais clara da linguagem. Isso fundamenta a esperança de que não se irá enganar ao escrever o autómato finito.
Escrito o autómato, este pode ser validado com base os exemplos que você escreveu (usando o predicado check_declaration/2, como se explica na secção "Validações"). Qualquer contradição entre o autómato e os testes unitários é assinalada com uma mensagem de erro. Esta técnica de verificação resulta bastante bem na prática pois se existir erro, o mais provável é que este se encontre no autómato e não nos exemplos. Mas mesmo que, afinal, o problema se situe nos exemplos, pelo menos você fica a saber que há um problema e vai tentar resolvê-lo.

Declaração de predicados

Cada predicado P-FLAT é obrigatoriamente definido usando um predicado Prolog com aridade 1. O predicado Prolog tem de ter o mesmo nome do predicado declarado.

Para exemplificar, eis a declaração completa do predicado evenP:

predicate(evenP, bitsA).

evenP(W) :- occurs(1, W, N), 0 is N mod 2.      % occurs/3 é um dos predicados sobre palavras disponível no P-FLAT

Os predicados constituem a forma mais directa de definir linguagens no P-FLAT. Um predicado P define directamente a linguagem {w: P(w)}).

Validações

Validação de declarações

Para validar uma declaração, usa-se o comando

:- execute(check_declaration(Name)).

onde Name representa o nome da entidade a validar.

Use sempre o comando check_declaration/1 após cada declaração. Assim, como neste exemplo:

re(evenRE, (0 + 1 * 0^* * 1)^*).
:- execute(check_declaration(evenRE)).

Vale a pena validar todas as declarações, pois são dezenas as situações inválidas e as situações suspeitas que o P-FLAT consegue detectar. As primeiras dão origem a mensagens de erro e as segundas dão origem a warnings.

só para dar uma ideia, eis apenas alguns dos muitos problemas que o P-FLAT detecta:

O mesmo nome está usado em duas declarações distintas.

Alfabeto contém símbolos proibidos.

Alfabeto está vazio.

Ordenação não é uma permutação de todos os símbolos do alfabeto indicado.

Linguagem declarada não tem qualquer testes unitário associado.

Teste unitário correspondente à palavra vazia não aparece.

Teste unitário refere uma palavra com símbolos fora do alfabeto indicado.

Expressão regular mal-formada.

Autómato finito sintacticamente errado.

Autómato finito sem estados finais.

Autómato finito sem transição inicial definida.

Autómato finito com estados inalcançáveis.

Gramática usa símbolos não-terminais para os quais não há produções.

Validação de definições

Para validar uma definição face a um conjunto de testes unitários, usa-se o comando

:- execute(test_definition(Def, Lang)).

onde Def representa uma entidade que supostamente caracteriza a linguagem Lang. A definição Def é validada face ao conjunto de testes unitários para Lang.

Use sempre o comando test_definition/2 após cada declaração, para validar a entidade declarada. Isto aplica-se a predicados, expressões regulares, autómatos finitos, gramáticas independentes do contexto, autómatos de pilha e máquinas de Turing.

Como para cada declaração é importante validar, não só a declaração, como também a entidade declarada, torna-se quase inevitável que cada declaração acabe por conduzir à escrita de três linhas. Assim:

re(evenRE, (0 + 1 * 0^* * 1)^*).
:- execute(check_declaration(evenRE)).
:- execute(test_definition(evenRE, evenL)).

Juntando tudo

Juntando tudo o que aprendemos até agora, eis um exemplo realista de script, cujo estilo você poderá imitar.

Neste script primeiro declara-se a linguagem evalL, escrevem-se diversos testes unitários para ela e valida-se a declaração. Seguidamente, declara-se a expressão regular evenRE, valida-se a correcção dessa declaração e valida-se a definição evenRE face à linguagem evenL. Só depois de ter tudo validado, é que se começam a fazer experiências com a expressão regular.

language(evenL, {0,1}).                         % Declara linguagem
in_language([], evenL, true).                   % Testes unitários
in_language([0,0,0], evenL, true).
in_language([1,1], evenL, true).
in_language([0,1,1], evenL, true).
in_language([1,1,0,0], evenL, true).
in_language([1,0,0,0,1,1,01], evenL, true).
in_language([1], evenL, false).
in_language([1,1,1], evenL, false).
in_language([1,0,0], evenL, false).
in_language([0,01], evenL, false).
in_language([1,0,0,1,1,0,0], evenL, false).
:- execute(check_declaration(evenL)).           % Valida declaração da linguagem (tem de ficar depois dos testes unitários)


re(evenRE, (0 + 1 * 0^* * 1)^*). % Declara expressão regular
:- execute(check_declaration(evenRE)).          % Valida declaração da expressão regular
:- execute(test_definition(evenRE, evenL)).     % Valida expressão regular face a linguagem

:- execute(show(evenRE)).                       % Mostra a expressão regular
:- execute(alpha(evenRE,A), A, true).           % Pede o alfabeto da expressão regular
:- execute(accept(evenRE, [1,1])).              % Pergunta se a palavra "11" pertence à linguagem definida pela expressão regular
:- execute(accept(evenRE, [0,1])).              % Pergunta se a palavra "10" pertence à linguagem definida pela expressão regular
:- execute(word(evenRE,A), A, length(A,4)).     % Gera palavras até aparecer a primeira com comprimento 4
:- execute(tracing(evenRE, [1,1])).             % Pede uma prova detalhada de que a palavra "11" pode ser obtida a partir da expressão regular

Predicados disponíveis

Predicados universais

Alguns dos predicados do P-FLAT aplicam-se a quase todas as entidades e por isso dizem-se predicados universais. Eis a documentação dos predicados universais, copiada directamente do ficheiro fonte do P-FLAT:

/*
alpha(?E,-A)                        The alphabet of entity E is A
show(?E)                            Display entity E
accept(?E, +W)                      E accepts W
accept(?E, +W, -Path)               E accepts W with execution path Path
word(?E, -W)                        E generates W
tracing(+E, +W)                     Trace E accepting W
*/

Predicados particulares

Outros predicados do P-FLAT só se aplicam a a entidades particulares, pelo que se dizem predicados particulares. Em muitos casos, o nome de cada predicado particular tem um prefixo que indica o tipo de entidade a que se aplica. Eis a documentação dos predicados particulares mais importantes, copiada directamente do ficheiro fonte do P-FLAT:

/*
prefix(?W1,+W2)                     Word W1 is a prefix of W2
suffix(?W1,+W2)                     Word W1 is a suffix of W2
subword(?W1,+W2)                    Word W1 is contained in W2
occurs(+S,+W,?N)                    Symbol S occurs N times in word W
lexically_ordered(?/+W1, +/?W2, ?O) W1 < W2 according to the lexical order
mixed_ordered(?W1, +W2, ?O)         W1 < W2 according to the "mixed" order

word_language(?W, +L)               W belongs to language expression L

re_fa(?RE, -FAE)                    Translates RE into expression FAE over finite automata
re_simplify(?RE1, -RE2)             RE2 is a simpler equivalent of RE1

fa_deterministic(?FA, ?Bool)        Bool says whether FA is deterministic of not
fa_re(+FAD, -RE)                    Translates deterministic FA into RE
fa_determine(?FA1, -FA2)            Transform non-deterministic FA1 into deterministic FA2
fa_rename(+FA1, -FA2)               FA2 is as FA1, but with all states renamed with new ids
fa_minimise(?FA1, -FA2)             The minimisation of FA1 is FA2
fa_compute(+FAE, -FA)               Evaluate expression FAE over finite automata, producing FA

cfg_normalize(?CFG, -CFG1)          CFG1 is a quasi-lambda-free and chain-free equivalent grammar

pda_deterministic(?PDA, ?Bool)      Bool says whether PDA is deterministic or not
pda_change_criterion(?PDA1, -PDA2)  Convert between the two acceptance criteria

tm_deterministic(?TM, ?Bool)        Bool says whether TM is deterministic or not
*/

Aprender mais sobre o P-FLAT

Se desejar ficar um perito no P-FLAT, então consulte o script "tutorial.pl" e observe o output a ser gerado ao mesmo tempo que estuda o código Prolog que lhe deu origem. É muito instrutivo.

Corra também o script "examples.pl".

Finalmente, a fonte de informação mais detalhada para o P-FLAT é o seu próprio código fonte. O código segue fielmente as definições apresentadas nas aulas teóricas e encontra-se profusamente comentado.