degreeStuff

Aula Pratica 1

Autómatos e Liguagens de Programação | Data: 09/02/2021; Hora:16:00; Duração: 1:45; Sala:CLAV_136;Docente: Francisco Coelho

Pagina Principal

Resolução de Exercicios

Exercício 03

Seja Σ={a,b}. Construa definições recursivas dos seguintes conjuntos:

$\C_1$ = {palavras sobre Σ tais que o símbolo a ocorre aos pares}. $\C_1$ inclui, por exemplo, bbaabbbaab e aaaaaaaa mas não inclui aaaaaa nem aabaaabaaabaaaba.

Base: $\aa$
Passo:
$\aap\in C_1$
$\paa\in C_1$
$\bp\in C_1$
$\pb\in C_1$
$\C_2 = p \in \Sigma^* : |p|$ é par , p começa por a e, em p , os a e os b ocorrem alternados }
$\C_3 =\{p \in \Sigma^*$ é caicua $\ \}$

Base: $\a, b$
Hipoteses:
$\color{green}\large\a, b$
$\color{green}\large\aa, bb,$ $\color{red}\large\ab, ba$
$\color{green}\large\aaa, bbb,aba,bab,$ $\color{red}\large\abb, baa,bba,aab$
Passo:
$\apa\in C_3$
$\bpb\in C_3$
$\c_4=\{a^nb^n\in \Sigma^* : n>0\}$

Base: $\ab$
Passo:
se $\p\in C_4$ então
$\apb\in C_4$
$\C_5 =\{a^ib^j\in \Sigma^* : 0\le i\le j \}$
$C_5$=

Base: $\a, b$
Hipoteses:
$\bb$
$\abb$
$\abbb$
Passo:
se $\p\in C_5$ então:
$\pb\in C_5$
$\apb\in C_5$
$\c_6=\{p\in\Sigma^*:|p|_a=|P|_b\}$

Base: $\a, b$
Passo:
$\apb\in C_6$
$\bpa\in C_6$

Exercicio 04

Encontre a menor palavra sobre o alfabeto $\Sigma =\{0\}$ que não está em $\{\lambda,0,0^2,0^5\}^3$ .
Não percebi be como se resolve o exercicio

Valor Esta calculo

0 ✓ $0$

1 ✓ $0$

2 ✓ $0^2$

3 ✓ $0^2 0=0^3$

4 ✓ $0^2 0^2=0^4$

5 ✓ $0^5$

6 ✓ ${0^2} 0^3=0^6$

7 ✓ $0^5 0^2=0^7$

8 ✓ $0^5 0^3=0^8$

9 ✓ $0^5 0^2 0^2=0^{5 2 2}=0^9$

10 ✓ ${0^5}^2=0^{2*5}=0^{10}$

11 ✓ $0^5 0^2 0^2 0^2=0^{11}$

12 ✓ $0^5 0^5 0^2=0^{12}$

13 $0$

14 $0$

15 ✓ ${0^5}^3=0^{5*3}=0^{15}$

Valor	Esta	calculo
0	✓	$0$
1	✓	$0$
2	✓	$0^2$
3	✓	$0^2 0=0^3$
4	✓	$0^2 0^2=0^4$
5	✓	$0^5$
6	✓	${0^2} 0^3=0^6$
7	✓	$0^5 0^2=0^7$
8	✓	$0^5 0^3=0^8$
9	✓	$0^5 0^2 0^2=0^{5 2 2}=0^9$
10	✓	${0^5}^2=0^{2*5}=0^{10}$
11	✓	$0^5 0^2 0^2 0^2=0^{11}$
12	✓	$0^5 0^5 0^2=0^{12}$
13		$0$
14		$0$
15	✓	${0^5}^3=0^{5*3}=0^{15}$

Logo o menor possivel $\{\lambda,0,0^2,0^5\}^3$ com $\Sigma =\{0\}$ é $0^{13}$

Pagina Principal Proxima Aula

This site is open source. Improve this page.