Subpalavra

---

Summary

Uma subpalavra é qualquer sequência contígua de símbolos dentro de uma palavra, incluindo a palavra vazia, prefixos, sufixos e trechos intermediários.

Dada uma palavra $w\in {\Sigma }^{\ast }$ sobre um alfabeto $\Sigma$, uma subpalavra (ou subcadeia) de $w$ é qualquer palavra $x\in {\Sigma }^{\ast }$ tal que existem palavras $u,v\in {\Sigma }^{\ast }$ (possivelmente vazias) satisfazendo:

$$w=uxv$$

A subpalavra $x$ é uma sequência contígua de símbolos dentro de $w$. Inclui $ϵ$, prefixos, sufixos e trechos intermediários.

Exemplo

Para a palavra $abcb$ temos os seguintes prefixos:

• $ϵ$
• $a$
• $b$
• $bcb$
• $bc$
• $\dots$

Referências

---

Aula 2 - Alfabetos palavras e linguagens