Aspectos Teóricos Lista 1

Cursos:

Bacharelado em Ciência da Computação e
Bacharelado em Sistemas de Informação
Disciplinas: (1493A) Teoria da Computação e Linguagens Formais,
(4623A) Teoria da Computação e Linguagens Formais e
(1601A) Teoria da Computação
Professora: Simone das Graças Domingues Prado [e-mail] e-mail: home-page: wwwp.fc.unesp.br/~simonedp/discipl.htm

Apostila 01 - Fundamentação da Teoria da Computação e
Linguagens Formais
Exercícios
1. Seja Σ o alfabeto {a,b}. Quais as linguagens abaixo?
(Liste as cadeias que pertencem a cada uma das linguagens)
i.
{ x ∈ Σ* | |x| é par } ii. { x ∈ Σ* | |x| ≤ 2 } iii. { x ∈ Σ* | o primeiro símbolo de x é igual ao último símbolo de x } iv. { x ∈ Σ* | o penúltimo caracter de x é a}
v.
{ x ∈ Σ* | x não contém a subcadeia aba } vi. { x ∈ Σ* | x não contém dois a consecutivos } vii. { x ∈ Σ* | x contém pelo menos dois a consecutivos } viii. { x ∈ Σ* | x contém no máximo dois a consecutivos } ix. { x ∈ Σ* | nenhum bloco de 3 caracteres consecutivos de x contém dois a }
x.
{ x ∈ Σ* | |x| = 0} xi. { x ∈ Σ* | |x| é ímpar e x é da forma yyR para algum y ∈ Σ*} xii. { xx | x ∈ Σ* } xiii. { xxR | x ∈ Σ* } xiv. { xyxR | x, y ∈ Σ* } xv. { aban b: n ≥ 0}
___________________________________________________________________________________________________
Teoria da Computação e Linguagens Formais - Simone Domingues Prado - Lista de Exercícios da Apostila 01

Página 1 de 2

2. Dadas as linguagens
L1 = { axa | x ∈ {a,b}* }
L2 = { xx | x ∈ {a,b}* }
(a) qual é a linguagem L1 ∪ L2 ?
(b) qual é a linguagem L1 ∩ L2 ?
(c) qual é a linguagem L1 ∪ L2 ?
(d)
(e)
(f)
(g)
(h)

qual é a linguagem L1 ∩ L2 ?
Qual é a linguagem L1 ο L2?
Qual é a linguagem L2 ο L1?
Qual é a linguagem (L1)*?
Qual é a linguagem (L2)*?

3. Qual a linguagem gerada?
(a) { w ∈ {a,b}* | w contenha exatamente dois símbolos as}
(b) { w ∈ {a,b}* | w contenha pelo menos dois símbolos bs}
(c) { w ∈ {a,b,c}* | w contenha pelo