SAGEMoLiC

Autores: A.H.R. da Silva and A.F. da Fonseca, R.B. Nogueira and M. Ayala-Rincón

SAGEMoLiC é fácil de usar!  Voce é guiado pelo conjunto de menus:

• File
• Language
• Edit
• Alphabet
• Operation
• Simulation
• Visualization

File inclui a opção Exit, uma coleção de interessantes exemplos pré-constroídos (Built-in Examples) e, muito importante, opções Open e Save que permitem salvar localmente os novos exemplos que sejam criados usando remotamente SAGEMoLiC. Desta forma, em subsequentes seções poderão ser reutilizados ditos exemplos.

Language aqui pode ser selecionado o tipo de linguagem. Atualmente entre regular language ou context-free language. A seleção default é regular language. Note que segundo a sua selação de classe de linguagens, os exemplos pré-constoídos serão ativados e os outros desativados.

Edit consiste de opções para criar autômatos finitos e autômatos à pilha de acordo à seleção do tipo de linguagem correspondente (Regular Language e Context Free Language, respectivamente).  Uma vez selecionado o tipo de linguagem (e esta seleção é essencial tanto para a construção de autômatos como para carregar os exemplos pré-construídos), voce poderá criar e eliminar estados e transicões entre estes.   Adicionalmente Edit inclui uma seleção Arrow que permite reposicionar tanto estados como transições.
Após seleção de Create Transition as transições entre estados são construídas selecionando com o botão esquerdo do mouse o estado de origem e  o de destino e um ponto intermediário onde será indicada a direção e o(s) símbolo(s) do alfabeto (e da pilha) desta.
Após criação dos estados clicando duas vezes nestes poderão ser definidos os estados finais e o inicial.

 Alphabet permite definir os símbolos do alfabeto (e os da pilha).  Uma vez selecionados estes, voce poderá incluir informação sobre os símbolos das transições clicando duas vezes nestas.

Edit e Alphabet podem ser utilizadas alternativamente na criação dos modelos computacionais (mas símbolos rotulando as transições poderão unicamente ser utilizados após ter sido definidos no alfabeto).

Operations

• para o caso das linguagens regulares permite transformar autômatos finitos não deterministas com transições epsilon em autômatos sem transições epsilon, deterministas e mínimos, passo a passo.  Além disso, neste menu, é possivel fornecer uma expressão regular, para a qual será criado o correspondente autômato finito (não determinista e com transições epsilon) que poderá eventulamente ser minimizado passo a passo.
• para o caso das linguagens livres de contexto permite a simulação do processo de derivação gramatical, translações às formas gramaticais normais de Greibach e Chomsky e translações diretas entre gramáticas e autômatos à pilha.

Simulation permite inserir palavras cujo processamento com o modelo atual sera ilustrado.

Visualization permite a ilustração gráfica dos princíos chave que fazem os modelos e representações gramaticais das linguagens regulares equivalentes. Somente as relações nao triviais são implementadas:

• Linguagens regulares
  • Lambda-NDFAs vs NFAs: nesta o usuário pode visualizar como uma sequência de transições de um estado a outro, que consiste de puras lambda-transições exceto por uma transição marcada com um símbolo do alfabeto, sea a, pode ser associada (e substituida) com uma única transição marcada com a, que vai do estado inicial ao final da sequência. A noção chave envolvida nesta equivalência, que é a de lambda fecho, é explicada e ilustrada. Adicionalmente, esta visualização ajuda a entender por que a existência de uma sequência de puras lambda-transições de um estado não-final a um estado final permite mudar o estado inicial da sequência de não-final para final. O anterior corresponde à atingibilidade ("for free") de estados finais desde um estado não-final ou equivalentemente à existência de estados finais no lambda fecho de um estado não-final.
  • DNFAs vs DFAs: o usuário pode visualizar como o não-determinismo em FAs corresponde &agrav; possibilidade de atingir subconjuntos de estados do conjunto inicial de estados. Partindo do estado inicial e examinando símbolo por símbolo do alfabeto, nuevos estados compostos vão sendo generados numa segunda canvas onde o DFA correspondente vai sendo gerado.
  • DFAs vs reduced DFAs: nesta o usuário pode visualizar as noções de estados distinguíveis e indistinguíveis, que justificam a existência de autômatos mínimos.
  • (Lambda-N)DFAs vs REs: nesta o usuário pode examinar detalhadamente como as transições originais de um autômato finito dado podem ser estendidas para transições equivalentes, cujas marcas são expressões regulares. E como este princípio básico de conversão permite construir uma expressão regular equivalente ao autômato finito inicial.
• Linguagens livres de contexto
  • CFG normalization to Greibach or Chomsky normal form: aqui o usuário pode observar passo a passo a conversão de gramáticas livres de contexto a suas formas normais de Chomsky ou Greibach.
  • CFG translation to pushdown automata: esta opção permite uma bela visualização da construção de autômatos à pilha desde gramáticas livres de contexto previamente convertidas na forma normal de Greibach.

• A representação gráfica de diagramas de transição para automatas que são generados após aplicar alguma translação não é clara, devido a que o sistema aleatoriamente seleciona posições livres da canvas em uso para colocar os estados e transições novos. Uma solução geométrica geral para este problema é muito difícil, já que esto está relacionado com a representação bi-dimensional eficiente de grafos. Para fazer claro o diagrama de transições em uso, o usuário pode, durante todo o processo de visualização ou de translação, re-posicionar estados e transições via uso simples do mause. Esto funciona sempre que a opcão Array do menu Edit este ativada.
• O tamanho das canvas muda de um browser para outro. Em particular, os botões de seleção Automatic Mode e Interactive Mode das diferentes canvas de controle no menu de visualization ficam escondidas sob alguns browsers. Para fazer visíveis tais botões o usuário pode aumentar o tamanho das correspondentes canvas via aplicação padrão do mouse.
• Tem-se detetado dificuldades ao tentar ativar alguns botões do SAGEMoLiC em plataformas linux como Red-Hat e Slakware. Está-se trabalhando para fazer o sistema o mais portável possível.