Computer Science › Algoritmos e Software
Quatro níveis aninhados de complexidade de gramática e linguagem (regular, livre de contexto, sensível ao contexto, e irrestrita) que organizam tudo o que o restante desta disciplina desenvolve com profundidade real para os dois primeiros.
Um conjunto de regras de produção, algumas referenciando a si mesmas, exatamente o formato autorreferencial já familiar da recursão, que geram cada string de uma linguagem uma substituição de cada vez.
Uma gramática é ambígua quando alguma string que ela gera tem mais de uma árvore de derivação válida, um problema real e prático para tudo que é construído sobre uma gramática, da precedência de operadores de uma calculadora ao parser de um compilador.
Toda gramática livre de contexto pode ser reescrita em uma forma onde cada regra tem exatamente um de dois formatos fixos, uma forma padronizada que viabiliza provas e algoritmos de parsing posteriores sem perder poder de geração.
Uma máquina com um conjunto finito de estados, sem memória além de qual estado ela ocupa, e exatamente uma transição por símbolo, o modelo formal de computação mais simples, e aquele que reconhece exatamente as linguagens regulares.
Uma máquina à qual é permitido ter várias transições para o mesmo símbolo ao mesmo tempo, ou nenhuma, aceitando quando ALGUMA escolha de caminho leva à aceitação, uma regra mais frouxa que acaba não acrescentando poder real.
Um NFA ao qual se dá exatamente um recurso extra, uma única pilha, que é precisamente a memória adicional suficiente para reconhecer toda linguagem livre de contexto, e nenhuma linguagem a mais.
Autômatos de pilha e gramáticas livres de contexto reconhecem exatamente a mesma classe de linguagens, dois formalismos de aparência muito diferente, um procedural e um generativo, que acabam sendo duas visões da mesma coisa.
Todo NFA, por mais emaranhado que seu não-determinismo pareça, pode ser convertido em um DFA equivalente rastreando todo estado em que o NFA PODERIA estar simultaneamente como um único novo estado, um resultado genuinamente surpreendente, demonstrado aqui por completo.
Combinar duas linguagens regulares com união, concatenação, ou estrela de Kleene sempre produz outra linguagem regular, um conjunto de garantias que tornam possível construir uma linguagem regular complexa a partir de peças simples, já conhecidas como regulares.
Uma notação compacta para descrever uma linguagem diretamente, construída a partir de símbolos únicos, concatenação, união, e repetição, o mesmo poder expressivo de um DFA, em uma forma que se lê como um padrão em vez de uma máquina.
Construindo um NFA para uma expressão regular peça por peça, espelhando exatamente sua estrutura, a metade construtiva e direta do teorema de Kleene, provando que toda expressão regular tem um autômato equivalente.
Toda linguagem regular tem um comprimento a partir do qual qualquer string longa o suficiente deve conter uma seção do meio repetível, um fato estrutural preciso e demonstrável cuja contrapositiva é a ferramenta padrão para provar que uma linguagem NÃO é regular.
A mesma ideia de bombeamento, um nível acima na hierarquia de Chomsky, uma string suficientemente longa em uma linguagem livre de contexto precisa ter duas partes repetíveis, bombeadas juntas, dando uma ferramenta padrão para provar que uma linguagem nem sequer é livre de contexto.
A direção mais difícil do teorema de Kleene, eliminar os estados de um DFA um de cada vez, construindo uma expressão regular que captura a mesma linguagem, até que reste apenas a própria expressão.
Dois retornos cotidianos e extremamente conhecidos de tudo o que foi coberto até aqui: ferramentas de busca e substituição executando expressões regulares compiladas, e a própria sintaxe de uma linguagem de programação definida e analisada por uma gramática livre de contexto.
Todo modelo coberto aqui (DFA, NFA, PDA) é fundamentalmente limitado: uma quantidade fixa de memória, ou memória com a forma de uma única pilha. A próxima disciplina remove esse limite por completo com a máquina de Turing.
Part of the Computer Science curriculum.
Quatro níveis aninhados de complexidade de gramática e linguagem (regular, livre de contexto, sensível ao contexto, e irrestrita) que organizam tudo o que o restante desta disciplina desenvolve com profundidade real para os dois primeiros.
Um conjunto de regras de produção, algumas referenciando a si mesmas, exatamente o formato autorreferencial já familiar da recursão, que geram cada string de uma linguagem uma substituição de cada vez.
Uma gramática é ambígua quando alguma string que ela gera tem mais de uma árvore de derivação válida, um problema real e prático para tudo que é construído sobre uma gramática, da precedência de operadores de uma calculadora ao parser de um compilador.
Toda gramática livre de contexto pode ser reescrita em uma forma onde cada regra tem exatamente um de dois formatos fixos, uma forma padronizada que viabiliza provas e algoritmos de parsing posteriores sem perder poder de geração.
Uma máquina com um conjunto finito de estados, sem memória além de qual estado ela ocupa, e exatamente uma transição por símbolo, o modelo formal de computação mais simples, e aquele que reconhece exatamente as linguagens regulares.
Uma máquina à qual é permitido ter várias transições para o mesmo símbolo ao mesmo tempo, ou nenhuma, aceitando quando ALGUMA escolha de caminho leva à aceitação, uma regra mais frouxa que acaba não acrescentando poder real.
Um NFA ao qual se dá exatamente um recurso extra, uma única pilha, que é precisamente a memória adicional suficiente para reconhecer toda linguagem livre de contexto, e nenhuma linguagem a mais.
Autômatos de pilha e gramáticas livres de contexto reconhecem exatamente a mesma classe de linguagens, dois formalismos de aparência muito diferente, um procedural e um generativo, que acabam sendo duas visões da mesma coisa.
Todo NFA, por mais emaranhado que seu não-determinismo pareça, pode ser convertido em um DFA equivalente rastreando todo estado em que o NFA PODERIA estar simultaneamente como um único novo estado, um resultado genuinamente surpreendente, demonstrado aqui por completo.
Combinar duas linguagens regulares com união, concatenação, ou estrela de Kleene sempre produz outra linguagem regular, um conjunto de garantias que tornam possível construir uma linguagem regular complexa a partir de peças simples, já conhecidas como regulares.
Uma notação compacta para descrever uma linguagem diretamente, construída a partir de símbolos únicos, concatenação, união, e repetição, o mesmo poder expressivo de um DFA, em uma forma que se lê como um padrão em vez de uma máquina.
Construindo um NFA para uma expressão regular peça por peça, espelhando exatamente sua estrutura, a metade construtiva e direta do teorema de Kleene, provando que toda expressão regular tem um autômato equivalente.
Toda linguagem regular tem um comprimento a partir do qual qualquer string longa o suficiente deve conter uma seção do meio repetível, um fato estrutural preciso e demonstrável cuja contrapositiva é a ferramenta padrão para provar que uma linguagem NÃO é regular.
A mesma ideia de bombeamento, um nível acima na hierarquia de Chomsky, uma string suficientemente longa em uma linguagem livre de contexto precisa ter duas partes repetíveis, bombeadas juntas, dando uma ferramenta padrão para provar que uma linguagem nem sequer é livre de contexto.
A direção mais difícil do teorema de Kleene, eliminar os estados de um DFA um de cada vez, construindo uma expressão regular que captura a mesma linguagem, até que reste apenas a própria expressão.
Dois retornos cotidianos e extremamente conhecidos de tudo o que foi coberto até aqui: ferramentas de busca e substituição executando expressões regulares compiladas, e a própria sintaxe de uma linguagem de programação definida e analisada por uma gramática livre de contexto.
Todo modelo coberto aqui (DFA, NFA, PDA) é fundamentalmente limitado: uma quantidade fixa de memória, ou memória com a forma de uma única pilha. A próxima disciplina remove esse limite por completo com a máquina de Turing.