Explique de que forma os conceitos de símbolo, alfabeto, cadeia e sentenças são usados para definir o conceito de linguagem formal.

Passo 1

O enunciado pede para mostrar como usamos os conceitos de símbolo, alfabeto, cadeia e sentença para chegar à definição de linguagem formal em Teoria de Autômatos e Linguagens Formais. Vamos precisar entender cada termo e então juntar tudo num conceito único.

Passo 2

Um símbolo é a unidade mais básica: pensa num caractere, como a, 0 ou \#. Em geral não dá para quebrar um símbolo em partes menores: ele é atômico.

Passo 3

Um alfabeto é um conjunto finito de símbolos. Denotamos geralmente por \Sigma. Por exemplo, \Sigma = \{0,1\} é o alfabeto binário, ou \Sigma = \{a,b,c\}. A finitude de \Sigma garante que toda sequência que formarmos venha desses símbolos que listamos.

Passo 4

Uma cadeia (ou string) sobre um alfabeto \Sigma é uma sequência finita de símbolos de \Sigma. Chamamos de \Sigma^* o conjunto de todas as cadeias (incluindo a cadeia vazia, dita \varepsilon). Por exemplo, se \Sigma = \{a,b\}, então ab, bba e \varepsilon são cadeias em \Sigma^*.

Passo 5

Em muitos contextos (especialmente em Lógica e Gramáticas), fala-se em sentença para destacar que determinada cadeia é bem-formada segundo regras específicas (por exemplo, uma fórmula lógica ou uma expressão aritmética). Mas, no sentido mais básico de Linguagens Formais, podemos identificar “sentenças” com cadeias em \Sigma^* que satisfazem algum critério de formação.

Passo 6

Finalmente, definimos linguagem formal como qualquer conjunto de cadeias sobre um alfabeto. Ou seja,
\mathcal{L} \subseteq \Sigma^*
é uma linguagem formal. As cadeias w\in\mathcal{L} são as sentenças dessa linguagem: tudo o que faz parte de \mathcal{L} está “bem-formado” segundo o critério que escolhemos (gramática, autômato, expressão regular etc.).

Resposta

Uma linguagem formal é um par (\Sigma,\mathcal{L}) em que \Sigma é um alfabeto finito de símbolos, \Sigma^* é o conjunto de todas as cadeias formadas por esses símbolos,
e \mathcal{L}\subseteq\Sigma^* é o conjunto das cadeias (ou sentenças) que pertencem à linguagem.

Exercícios relacionados