---
title: Linguagens e gramatica
description: Linguagens e gramatica
tags: Linguagens formais e Autômatos
---
# Linguagens
* Toda linguagem tem uma gramatica associada a ela
* Toda gramatica gera um conjunto de palavras
### Oque é?
Para definir uma linguagem, necessario entender o conceito de **alfabeto**, **palavra** e **cadeia de caracteres**
* **Caractere**, Simbolo: Equivalente a um simbolo único: 'a', 'b', '1', '+';
* **Alfabeto, Σ**: Conjunto **finito** de simbolos ou caracteres: ['aasa', 'bdss', '1', '+'](4 elementos) ou [(conjunto vazio = λ)](o elementos);
* **Palavra, Cadeia, Sentença**: Conjunto **finito** de simbolos ou caracteres: ['ab1+'](4 simbolos) ou ['λ'](0 simbolos)

### Préfixo vs Sufixo vs Subpalavra
Toda palavra tem prefixo e sufixo.
Dada a palavara: apartamento
* **Prefixos**: λ, A, Ap, Apa, Apar, Apart...
* **Sufixos**: λ, o, to, nto, ento, mento...
* **Subpalavra**: Todos os sufixos e prefixos
### Concatenação de palavras
* **Associativa**: A palavra não muda ao correr o parentes: v(wt) = (vw)t
* **Elemento neutro**: concatenar a palavra com λ, gera a propia palavra;
* **Concatenação sucessiva**: Palavra^0 = λ, Palavra^2 = Palavra + Palavra
### Σ* vs Σ+
* **Σ***: Conjunto de todas palavras(w) possiveis do alfabeto(w ∈ Σ*), ele é **infinito**
* **Σ+**: Conjunto de toas palavras(w) exceto o λ, ele é **infinito**
### Comprimento e tamanho de palavra
Se da pelo numero de caracteres presentes numa palavra
### Lingaugem formal (L)
* L, é um conjunto **finito** de palavras
* As palavras de uma lingaugem, são formadas com os simbolos de um alfabeto
* Conjunto vazio é diferente de palavra vazia
### Palindromos
São palavras que tem a mesma leitura não importando o sentido da leitura.
λ, aa, bbb, cccc, abcba
### Operações de conjunto
### Gramatica
### Automato aceitador deterministico (DFA)