Trabalho Linguagens Formais e Automatos

1. Para o conjunto A = {∅, a , {a}}, calcule o conjunto potência B = , e então obtenha A X B, A∪B e A∩B .
B = → Conjunto de todos os subconjuntos possíveis de serem obtidos a partir de A. Logo, B = {∅ , a , {a}, {∅}, {∅ ,a}, {∅ , {a}}, {∅ , {a, {a}}, {a, {a}}}.
A x B = { (∅, ∅), (∅, a), (∅, {a}), (∅, {∅}), (∅, {∅, a}), (∅, {∅, {a}}), (∅, {∅, {a, {a}}}), (∅, {a, {a}}), (a, ∅), (a, a), (a, {a}), (a, {∅}), (a, {∅, a}), (a, {∅, {a}}), (a, {∅, {a, {a}}}), (a, {a, {a}}), ({a}, ∅), ({a}, a), ({a}, {a}), ({a}, {∅}), ({a}, {∅, a}), ({a}, {∅, {a}}), ({a}, {∅, {a, {a}}}), ({a}, {a, {a}}) }
A∪B = B = { ∅ , a , {a}, {∅}, {∅ ,a}, {∅ , {a}}, {∅ , {a, {a}}, {a, {a}}}.
A∩B = A = { ∅ , a , {a}}
3. Defina, com suas palavras, o que você entende por linguagem. Cite três maneiras distintas através das quais se podem definir linguagens, mencionando as características, principais aplicações, vantagens e desvantagens de cada método. Em seguida, explique o que significa definir formalmente uma linguagem. Apresente pelo menos dois motivos que justifiquem a importância de se definir linguagens formalmente.
Linguagem é um conjunto de cadeias (frases) que são formadas pela concatenação de símbolos (palavras) pertencentes à um determinado alfabeto e que atendem ao conjunto de propriedades (regras) da própria linguagem.
As três maneiras distintas que se pode definir uma linguagem são: gramáticas, reconhecedores e enumerações.
Gramáticas: geram um conjunto de cadeias que compõem uma determinada linguagem baseado em regras de substituição. É aplicável para linguagens finitas e infinitas. As vantagens desse método são que não são geradas cadeias que não pertencem à linguagem, pode ser empregada em linguagens infinitas e possibilita uma boa percepção da estrutura sintática das sentenças das linguagens.
Reconhecedores: é um dispositivo de aceitação de cadeias de acordo com as especificações da linguagem. Aceita e rejeita cadeias que, respectivamente, pertencem e não pertencem à