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
,
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
. Por exemplo,
é o alfabeto binário, ou
. A finitude de
garante que toda sequência que formarmos venha desses símbolos que listamos.
Passo 4
Uma cadeia (ou string) sobre um alfabeto
é uma sequência finita de símbolos de
. Chamamos de
o conjunto de todas as cadeias (incluindo a cadeia vazia, dita
). Por exemplo, se
, então
,
e
são cadeias em
.
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
que satisfazem algum critério de formação.
Passo 6
Finalmente, definimos linguagem formal como qualquer conjunto de cadeias sobre um alfabeto. Ou seja,
é uma linguagem formal. As cadeias
são as sentenças dessa linguagem: tudo o que faz parte de
está “bem-formado” segundo o critério que escolhemos (gramática, autômato, expressão regular etc.).
Resposta
Uma linguagem formal é um par
em que
é um alfabeto finito de símbolos,
é o conjunto de todas as cadeias formadas por esses símbolos,
e é o conjunto das cadeias (ou sentenças) que pertencem à linguagem.
e