Mapa Mental - Linguagens Formais

Prévia do material em texto

Gramáticas Formais Gramáticas Regulares Gramáticas à direita Definidas por quatro parâmetros: V, Σ, P e S, que substituem não terminais por estruturam a gramática. terminais seguidos de não terminais. Símbolos terminais e não terminais compõem alfabeto Gramáticas à esquerda da gramática. substituem não terminais por Regras de substituição (P) terminais precedidos de não terminais. determinam como cadeias são geradas. Gramáticas lineares à esquerda Símbolo inicial (s) é a raiz e à direita são equivalentes em poder expressivo. para derivação das cadeias da linguagem. São usadas para descrever linguagens regulares e construir autômatos Linguagens correspondentes. Autômatos Finitos Expressões Regulares Reconhecem linguagens Formais Utilizam operadores como regulares por meio de concatenação, união e fecho de estados e transições. Kleene para definir Estado inicial e estados linguagens. finais definem aceitação de Podem gerar cadeias com cadeias de entrada. padrões específicos, como Execução do autômato repetições e combinações. percorre estados conforme Expressões regulares são símbolos da cadeia. equivalentes a autômatos Podem ser representados finitos na definição de graficamente para facilitar linguagens. entendimento. Reconhecimento de Cadeias Permitem identificar cadeias Autômatos processam cadeias que pertencem ou não a uma símbolo a símbolo, transitando linguagem regular. entre estados. Linguagens Regulares Aceitação ocorre se a cadeia termina em um estado final após Hierarquia de Chomsky Podem ser descritas por todas transições. Classifica linguagens em quatro autômatos finitos, gramáticas Cadeias inválidas são rejeitadas tipos: regulares, livres de regulares e expressões quando não alcançam estado final contexto, sensíveis ao contexto regulares. adequado. e irrestritas. Expressões regulares definem Análise de cadeias permite validar Linguagens regulares são O tipo padrões para geração de se pertencem à linguagem definida 3, as mais restritas e simples cadeias válidas. pelo autômato. da hierarquia. Fecho de Kleene permite Linguagens de programação repetição ilimitada de geralmente pertencem aos tipos símbolos ou grupos. 2 (livres de contexto) e 3. Linguagens regulares são as Linguagens naturais são mais simples dentro da classificadas como tipo 1, mais hierarquia de Chomsky. complexas que as regulares.