Exercício 01.03.35

Segundo Ramos (2009), uma palavra α é uma subpalavra de outra palavra β se for possível escrever β como sendo γαδ, admitindo-se a possibilidade de γ ou δ ou ambos serem palavras vazias (ε). Note que prefixos (γ) e sufixos (δ) são casos particulares de subpalavras (α).

A Tabela 01 apresenta as subpalavras (α) da palavra palíndromo (β), conforme a definição apresentada por Ramos (2009).

Tabela 01: subpalavras da palavra **palíndromo**
\|`γ`\|	\|`α`\|	\|`δ`\|	`β`	`γ`	`α`	`δ`
0	0	10	palíndromo	ε	ε	palíndromo
0	1	9	palíndromo	ε	p	alíndromo
1	1	8	palíndromo	p	a	líndromo
2	1	7	palíndromo	pa	l	índromo
3	1	6	palíndromo	pal	í	ndromo
4	1	5	palíndromo	palí	n	dromo
5	1	4	palíndromo	palín	d	romo
6	1	3	palíndromo	palínd	r	omo
7	1	2	palíndromo	palíndr	o	mo
8	1	1	palíndromo	palíndro	m	o
9	1	0	palíndromo	palíndrom	o	ε
0	2	8	palíndromo	ε	pa	líndromo
1	2	7	palíndromo	p	al	índromo
2	2	6	palíndromo	pa	lí	ndromo
3	2	5	palíndromo	pal	ín	dromo
4	2	4	palíndromo	palí	nd	romo
5	2	3	palíndromo	palín	dr	omo
6	2	2	palíndromo	palínd	ro	mo
7	2	1	palíndromo	palíndr	om	o
8	2	0	palíndromo	palíndro	mo	ε
0	3	7	palíndromo	ε	pal	índromo
1	3	6	palíndromo	p	alí	ndromo
2	3	5	palíndromo	pa	lín	dromo
3	3	4	palíndromo	pal	índ	romo
4	3	3	palíndromo	palí	ndr	omo
5	3	2	palíndromo	palín	dro	mo
6	3	1	palíndromo	palínd	rom	o
7	3	0	palíndromo	palíndr	omo	ε
0	4	6	palíndromo	ε	palí	ndromo
1	4	5	palíndromo	p	alín	dromo
2	4	4	palíndromo	pa	línd	romo
3	4	3	palíndromo	pal	índr	omo
4	4	2	palíndromo	palí	ndro	mo
5	4	1	palíndromo	palín	drom	o
6	4	0	palíndromo	palínd	romo	ε
0	5	5	palíndromo	ε	palín	dromo
1	5	4	palíndromo	p	alínd	romo
2	5	3	palíndromo	pa	líndr	omo
3	5	2	palíndromo	pal	índro	mo
4	5	1	palíndromo	palí	ndrom	o
5	5	0	palíndromo	palín	dromo	ε
0	6	4	palíndromo	ε	palínd	romo
1	6	3	palíndromo	p	alíndr	omo
2	6	2	palíndromo	pa	líndro	mo
3	6	1	palíndromo	pal	índrom	o
4	6	0	palíndromo	palí	ndromo	ε
0	7	3	palíndromo	ε	palíndr	omo
1	7	2	palíndromo	p	alíndro	mo
2	7	1	palíndromo	pa	líndrom	o
3	7	0	palíndromo	pal	índromo	ε
0	8	2	palíndromo	ε	palíndro	mo
1	8	1	palíndromo	p	alíndrom	o
2	8	0	palíndromo	pa	líndromo	ε
0	9	1	palíndromo	ε	palíndrom	o
1	9	0	palíndromo	p	alíndromo	ε
0	10	0	palíndromo	ε	palíndromo	ε

Conforme apresentado na Tabela 01, as subpalavras (α) da palavra palíndromo (β) são formalmente definidas como:

{ε, a, d, l, m, n, o, p, r, í, al, dr, lí, mo, nd, om, pa, ro, ín, alí, dro, lín, ndr, omo, pal, rom, índ, alín, drom, línd, ndro, palí, romo, índr, alínd, dromo, líndr, ndrom, palín, índro, alíndr, líndro, ndromo, palínd, índrom, alíndro, líndrom, palíndr, índromo, alíndrom, líndromo, palíndro, alíndromo, palíndrom, palíndromo}

Referências Bibliográficas

Ramos, Marcus Vinícius Midena. (2009). Linguagens Formais: teoria, modelagem e implementação. Porto Alegre: Bookman. 656 páginas.

Tutoriais - Linguagens Formais e Autômatos
Tutoriais
Linguagens Formais e Autômatos

Solução do Exercício

Referências Bibliográficas

Tutoriais - Linguagens Formais e AutômatosTutoriaisLinguagens Formais e Autômatos