# Propriedades das livres de contexto

Simplificação de CFG, forma normal de Chomsky, CYK, fecho e lema da repetição.

Página: https://resumos.rgo.pt/cadeiras/tc/propriedades-livres/

Em $S\to AB$, se $A$ puder desaparecer, $B$ também tem de poder gerar sozinho uma palavra a partir do início. Apagar $A\to\varepsilon$ sem acrescentar $S\to B$ perderia essa possibilidade.

A simplificação substitui o efeito das regras que elimina. Depois, a forma normal de Chomsky organiza as [produções de CFG](https://resumos.rgo.pt/cadeiras/tc/gramaticas-livres/#defini%C3%A7%C3%A3o-e-deriva%C3%A7%C3%B5es) para calcular a pertença numa tabela.

## Variáveis anuláveis, unitárias e inúteis

Uma variável é **anulável** se deriva $\varepsilon$. Começa nas produções $A\to\varepsilon$ e acrescenta uma variável quando alguma das suas produções contém apenas variáveis já anuláveis. Repete até estabilizar. Um terminal nunca é anulável.

Para eliminar produções vazias, cria todas as combinações de presença e ausência das ocorrências anuláveis em cada lado direito. Em $A\to BCB$, se $B$ for anulável e $C$ não for, surgem $BCB$, $CB$, $BC$ e $C$. As duas ocorrências de $B$ são escolhas independentes. Depois retira produções vazias, tratando separadamente a aceitação de $\varepsilon$.

Uma produção **unitária** tem forma $A\to B$, com duas variáveis. Calcula os pares $(A,B)$ em que $A$ chega a $B$ só com produções unitárias, incluindo $(A,A)$. Copia para $A$ todas as produções não unitárias de cada $B$ alcançado e retira as unitárias. Não basta apagar $A\to B$, porque perderias as palavras geradas através dela.

Uma variável é **geradora** se deriva alguma palavra terminal. Calcula primeiro as geradoras, a partir de regras só com terminais ou variáveis já geradoras. Retira as não geradoras e as regras que as usam. Depois calcula as variáveis alcançáveis a partir do início na gramática que ficou e retira as restantes.

Por exemplo, em $S\to AB\mid a$, $A\to b$, sem regras para $B$, $B$ não é geradora. Retira $S\to AB$ e, só depois, vês que $A$ ficou inacessível. O resultado é $S\to a$.

Uma ordem segura para a simplificação completa é: eliminar produções vazias, eliminar unitárias e eliminar símbolos inúteis, primeiro não geradores e depois inacessíveis. A eliminação de vazias pode criar unitárias, e as etapas podem tornar símbolos inúteis.

### Simplificação acompanhada numa gramática

Considera a gramática

$$
S\to AB\mid a,\quad A\to b\mid\varepsilon,\quad B\to C,\quad C\to cC\mid c,\quad D\to d.
$$

1.  Só $A$ é anulável. Em $S\to AB$, omitir $A$ cria $S\to B$. Retira depois $A\to\varepsilon$.
2.  Agora há as unitárias $S\to B$ e $B\to C$. A cadeia chega de $S$ a $C$, pelo que copiamos $cC$ e $c$ para **ambos** $S$ e $B$, e retiramos as duas unitárias.
3.  Todas as variáveis são geradoras, mas $D$ é inacessível a partir de $S$ e sai.

O resultado completo é:

$$
S\to AB\mid a\mid cC\mid c,\quad A\to b,\quad B\to cC\mid c,\quad C\to cC\mid c.
$$

$bc$ continua a derivar por $S\Rightarrow AB\Rightarrow bB\Rightarrow bc$. A palavra $c$, que antes dependia de apagar $A$, deriva agora diretamente por $S\Rightarrow c$. A linguagem mantém-se $(\varepsilon+b)cc^*+a$.

### Intercalação de uma CFL com uma regular

Se $L$ é CFL e $R$ é regular, a intercalação $inter(L,R)$ é CFL. A construção usa um PDA $P$ por estado final para $L$ e um DFA $D$ para $R$:

1.  Usa um fundo novo, que a simulação de $P$ não retira, para permitir ler letras de $R$ mesmo depois de a pilha simulada ficar vazia.
2.  Constrói um PDA cujo estado é $(p,q)$: ao ler uma letra, escolhe avançar $P$ mantendo $q$, ou avançar $D$ mantendo $p$ e a pilha. Transições vazias de $P$ mantêm $q$.
3.  Aceita quando $p$ é final em $P$, $q$ é final em $D$ e a entrada foi consumida.

Cada letra é atribuída a uma das duas palavras, preservando a ordem interna de cada uma. Isto generaliza a construção para intercalação regular/regular, onde dois DFA chegam; aqui a pilha de $P$ acompanha apenas as letras atribuídas a $L$.

## Forma normal de Chomsky

Na **forma normal de Chomsky**, CNF, as produções têm forma

$$
A\to BC\quad\text{ou}\quad A\to a.
$$

Adota a extensão que permite $S_0\to\varepsilon$ se a linguagem contém a palavra vazia, desde que o início $S_0$ não apareça em nenhum lado direito. Uma regra $S_0\to S$ é unitária e não fica na CNF final desta convenção.

Depois da simplificação, substitui cada terminal em lados direitos de comprimento pelo menos dois por uma variável nova, como $T_a\to a$. Não alteres $A\to a$, que já está na forma certa.

Divide os lados direitos compridos: $A\to BCD$ torna-se $A\to BX$, $X\to CD$, com $X$ novo. Para quatro ou mais variáveis, continua a cadeia. Cada regra passa a ter duas variáveis ou um terminal.

### Conversão completa

Parte de $S\to aSb\mid\varepsilon$. Introduz $A\to a$, $B\to b$, ficando $S\to ASB\mid\varepsilon$. O início $S$ é anulável e aparece à direita; cria um início novo $S_0$ para preservar $\varepsilon$.

Eliminando a ocorrência anulável de $S$ no meio, tens $S\to ASB\mid AB$. Copia estas regras para $S_0$ para eliminar $S_0\to S$, e conserva $S_0\to\varepsilon$. Finalmente, divide $ASB$ com $C\to SB$:

$$
\begin{aligned} S_0&\to AC\mid AB\mid\varepsilon,\\ S&\to AC\mid AB,\\ C&\to SB,\\ A&\to a,\qquad B\to b. \end{aligned}
$$

$S_0$ não aparece à direita. Para $aabb$, a derivação é $S_0\Rightarrow AC\Rightarrow aC\Rightarrow aSB\Rightarrow aABB\Rightarrow aaBB\Rightarrow aabB\Rightarrow aabb$. A base $AB$ dá um par, e $AC$ acrescenta outro par à volta.

## CYK: decidir a pertença

O algoritmo **CYK** usa uma CFG em CNF e uma palavra não vazia $w=a_1\cdots a_n$. A célula $T[i,j]$ contém as variáveis que geram a subpalavra $a_i\cdots a_j$.

Na diagonal:

$$
T[i,i]=\{A\mid A\to a_i\}.
$$

Para intervalos maiores, tenta todos os cortes $k$ entre $i$ e $j$. Se $A\to BC$, $B\in T[i,k]$ e $C\in T[k+1,j]$, acrescenta $A$ a $T[i,j]$. Preenche por comprimento crescente, porque cada decisão depende de intervalos menores.

Com a CNF anterior e $aabb$, obténs a tabela abaixo por comprimento crescente. Os índices $[i,j]$ identificam as posições da subpalavra na entrada:

| Intervalo e palavra | Variáveis |
| --- | --- |
| $[1,1]: a$ | $\{A\}$ |
| $[2,2]: a$ | $\{A\}$ |
| $[3,3]: b$ | $\{B\}$ |
| $[4,4]: b$ | $\{B\}$ |
| $[1,2]: aa$ | $\emptyset$ |
| $[2,3]: ab$ | $\{S_0,S\}$ |
| $[3,4]: bb$ | $\emptyset$ |
| $[1,3]: aab$ | $\emptyset$ |
| $[2,4]: abb$ | $\{C\}$ |
| $[1,4]: aabb$ | $\{S_0,S\}$ |

Em $abb$, o corte $ab\mid b$ usa $C\to SB$. Em $aabb$, o corte $a\mid abb$ usa $S_0\to AC$. Como $S_0\in T[1,4]$, a palavra pertence à linguagem.

Não juntes todos os símbolos de uma linha sem respeitar o intervalo e o corte. $B$ no último $b$ só pode combinar com uma variável que gere a parte imediatamente anterior no mesmo intervalo.

Para gramática fixa, há $O(n^2)$ células e $O(n)$ cortes por célula, dando tempo $O(n^3)$ e espaço $O(n^2)$. Se a gramática variar, o custo inclui também o número de produções. Para $\varepsilon$, não crias uma tabela vazia: verifica diretamente se o início pode gerar a palavra vazia.

## Propriedades de fecho

As livres de contexto são fechadas para união, concatenação, estrela e reverso. Para união, usa um início novo $S\to S_1\mid S_2$, após renomear variáveis para os conjuntos serem disjuntos. Para concatenação, usa $S\to S_1S_2$; para estrela, usa $S\to S_1S\mid\varepsilon$.

São também fechadas para interseção com uma **regular**. O produto entre PDA e DFA guarda ambos os estados, conservando a pilha do PDA. Uma transição vazia do PDA não altera o estado do DFA; uma letra lida atualiza ambos. Aceita quando as duas condições finais se verificam após consumir a entrada.

Não são fechadas para interseção entre duas CFL. Considera:

$$
L_1=\{a^nb^nc^m\mid n,m\ge0\},\qquad L_2=\{a^mb^nc^n\mid n,m\ge0\}.
$$

Cada uma compara apenas dois blocos, mas a interseção é $\{a^nb^nc^n\mid n\ge0\}$, que não é livre de contexto. Também não há fecho geral para complemento: se houvesse, as leis de De Morgan e o fecho para união dariam fecho para interseção. A diferença geral falha pela mesma razão, pois $\Sigma^*\setminus L$ é um caso de diferença.

## Lema da repetição para CFL

Se $L$ é livre de contexto, existe $p\ge1$ tal que toda a palavra $s\in L$, $|s|\ge p$, admite $s=uvwxy$ com:

$$
|vwx|\le p,\qquad |vx|\ge1,\qquad \forall i\ge0,\ uv^iwx^iy\in L.
$$

A condição $|vx|\ge1$ permite que uma das partes seja vazia, mas não ambas; bombeia $v$ e $x$ com o mesmo expoente, enquanto $w$ fica uma única vez. Ao contrário do lema regular, a zona limitada não tem de estar no princípio da palavra.

Uma árvore sintática suficientemente alta repete uma variável num caminho. Podes retirar a parte entre as duas ocorrências, ou repeti-la. Essa parte acrescenta $v$ de um lado da subárvore interior e $x$ do outro. Uma CNF permite limitar o tamanho da zona que contém a repetição.

### Provar que aⁿbⁿcⁿ não é CFL

Supõe que $L=\{a^nb^nc^n\mid n\ge0\}$ é CFL e seja $p$ o comprimento do lema. Escolhe $s=a^pb^pc^p$. Considera qualquer decomposição válida.

Como $|vwx|\le p$, essa zona não pode conter ao mesmo tempo um $a$ e um $c$: teria de incluir todo o bloco de $p$ letras $b$, além dos dois extremos. Logo, a zona deixa intacto pelo menos um dos tipos de símbolo extremos.

Com $i=0$, retiras $v$ e $x$. Retiras pelo menos um símbolo, pois $|vx|\ge1$, enquanto o tipo que não aparece na zona mantém as suas $p$ ocorrências. As três contagens já não são iguais. Portanto, $uwy\notin L$, contradizendo o lema.

Não escolhes uma decomposição conveniente. A limitação da zona cobre todas as decomposições. Como no lema regular, satisfazer o lema não prova pertença à classe.

### A palavra escolhida pode admitir uma repetição

Estar na linguagem e ter comprimento suficiente são condições necessárias para uma testemunha, mas não chegam para a prova negativa. Considera

$$
K=\{a^nb^nz\mid n\ge0,\ z\in\{a,b\}^n\}.
$$

O último bloco tem comprimento $n$, mas as suas letras são livres. Não exige três contagens iguais de símbolos diferentes.

Supondo $K$ CFL, recebe o comprimento $p$ do lema. Podemos aumentá-lo para $p\ge3$, pois a condição continua válida com um limite maior. A candidata $a^pb^{2p}$ pertence a $K$, escolhendo $z=b^p$. Porém, admite um corte que o adversário pode usar para escapar à contradição:

$$
u=a^{p-1},\quad v=a,\quad w=\varepsilon,\quad x=bb,\quad y=b^{2p-2}.
$$

O corte tem $|vwx|=3\le p$ e $|vx|=3>0$. Para qualquer expoente $i\ge0$, a palavra bombeada é

$$
a^{p-1+i}b^{2(p-1+i)}.
$$

Continua em $K$, com $n=p-1+i$ e bloco final $z=b^n$. Encontrámos um corte que impede a contradição com esta candidata. Isto não prova que $K$ seja CFL; mostra que precisamos de escolher outra palavra.

### Separar a zona curta dos extremos

Escolhe agora $s=a^{2p}b^{2p}a^{2p}\in K$. A zona $vwx$ tem comprimento no máximo $p$ e não pode tocar nos dois blocos de $a$, pois teria de atravessar os $2p$ símbolos $b$. É esta a testemunha que funciona: força o adversário a retirar símbolos de uma região que desequilibra sempre a palavra.

Bombeia com $i=0$. Seja $\alpha$ a quantidade retirada do primeiro bloco, $\beta$ do bloco de $b$ e $\gamma$ do último. A palavra fica $a^jb^ka^\ell$, com

$$
j=2p-\alpha,\quad k=2p-\beta,\quad\ell=2p-\gamma.
$$

Todos os blocos continuam não vazios, porque retiramos no máximo $p$ símbolos. Para pertencer a $K$, a primeira mudança de $a$ para $b$ fixa $n=j$. É preciso ter $k\ge j$ letras $b$ para o bloco obrigatório. O que sobra, $b^{k-j}a^\ell$, deve ter comprimento $j$, portanto $k+\ell=2j$.

Estas condições excluem todos os cortes:

| Zona que contém as partes retiradas | Condição que falha |
| --- | --- |
| Não retira do primeiro bloco, $\alpha=0$ | $\beta+\gamma>0$ dá $k+\ell<4p=2j$. |
| Retira do primeiro bloco, $\alpha>0$ | O último fica intacto, $\gamma=0$. A igualdade exigiria $\beta=2\alpha$, mas $k\ge j$ exigiria $\beta\le\alpha$. São incompatíveis. |

Como $v,x$ não são ambos vazios, algum símbolo sai. Em qualquer decomposição válida, a palavra bombeada deixa $K$. Esta contradição prova que $K$ não é CFL. A prova usa o significado do último bloco, não uma falsa exigência de que contenha só $a$.

## O que se pode decidir sobre CFG

A pertença é decidível por CYK. O vazio é decidível verificando se o início é gerador. Já não há algoritmos gerais que decidam equivalência de duas CFG, universalidade de uma CFG ou ambiguidade de uma CFG.

Isto não impede resolver exemplos particulares com um argumento. Dizer que um problema é indecidível significa que não existe um algoritmo que termine e responda corretamente a **todas** as entradas desse problema.

## Exercícios

A prova de três contagens adapta a linguagem da questão 11 do teste de 13/6/2024. A intercalação adapta a TP de 2022/23, como indicado no enunciado. As gramáticas de CNF e CYK são próprias.

Provar que duas comparações não chegam

Prova que $L=\{a^nb^nc^{2n}\mid n\ge1\}$ não é livre de contexto.

Pista

A zona vwx tem comprimento no máximo p e não pode tocar simultaneamente em a e c.

Mais uma pista

Se toca em a e/ou b sem c, as contagens de a e b não podem continuar ambas iguais a metade de 2p. Se toca em b e/ou c sem a, o a fica em p.

Solução

Supõe L CFL, recebe p e escolhe $a^pb^pc^{2p}$. Para qualquer decomposição válida, vwx não contém simultaneamente a e c. Com i=0 retira-se pelo menos um símbolo. Se não há c na zona, o número de c fica em 2p; manter a relação exigiria que a e b continuassem ambos em p, impossível porque algum deles foi retirado. Se não há a na zona, a fica em p; manter a linguagem exigiria b=p e c=2p, novamente impossível porque algum b ou c foi retirado. Logo a palavra bombeada sai de L em todos os casos.

Confere a tua resposta:

*   Escolhe a elevado a p, b elevado a p e c elevado a 2p.
*   Usa o limite da zona para garantir que algum tipo extremo fica intacto.
*   Bombeia com i=0 e mostra que a igualdade a=b ou a relação c=2a falha.

Erros frequentes

Não esqueças que v ou x pode ser vazio. Não exijas que vwx esteja no princípio da palavra.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/propriedades-livres/#lema-da-repeti%C3%A7%C3%A3o-para-cfl)

Preservar a palavra vazia

Converte em CNF, preservando a linguagem, a gramática $S\to AB\mid a$, $A\to aA\mid\varepsilon$, $B\to b\mid\varepsilon$. Explica o tratamento de $\varepsilon$.

Pista

A linguagem é a estrela de a seguida de zero ou um b. A CNF tem de conservar a palavra vazia.

Mais uma pista

$S$ nunca aparece num lado direito, pelo que podes manter $S\to\varepsilon$ como exceção inicial.

Solução

As variáveis anuláveis são $A,B,S$. Ao omitir as ocorrências de $AB$, surgem $AB,A,B,\varepsilon$. Ao omitir $A$ de $aA$, surge $a$. Depois de retirar as vazias de $A,B$ e eliminar as unitárias $S\to A,B$, obtemos

$$
S\to AB\mid aA\mid a\mid b\mid\varepsilon,\qquad A\to aA\mid a,\qquad B\to b.
$$

Introduzindo $T\to a$, a CNF final é

$$
S\to AB\mid TA\mid a\mid b\mid\varepsilon,\qquad A\to TA\mid a,\qquad B\to b,\qquad T\to a.
$$

$S$ não aparece à direita, pelo que a exceção vazia é válida. $AB$ gera um ou mais $a$ seguidos de $b$, $TA$ gera pelo menos dois $a$, e as bases cobrem $a,b,\varepsilon$. A linguagem continua $a^*(\varepsilon+b)$.

Confere a tua resposta:

*   Identifica A, B e S como anuláveis.
*   Acrescenta as alternativas resultantes de omitir A ou B antes de eliminar as vazias.
*   Elimina unitárias e substitui o a de aA por uma variável.
*   Mantém ε apenas no início, ausente dos lados direitos.

Erros frequentes

Não apagues ε da linguagem. Não deixes S→A ou S→B na CNF. Não substituas S→a: já é uma produção válida.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/propriedades-livres/#vari%C3%A1veis-anul%C3%A1veis-unit%C3%A1rias-e-in%C3%BAteis)

Tentar todos os cortes

Na CNF $S\to AB\mid AC$, $C\to SB$, $A\to a$, $B\to b$, calcula a tabela CYK para $aab$. A palavra é aceite? Indica cada corte que produz um conjunto não vazio.

Pista

A regra S→AC requer C no intervalo da direita, não S.

Mais uma pista

Os cortes do intervalo total são $a\mid ab$ e $aa\mid b$.

Solução

A diagonal é $\{A\},\{A\},\{B\}$. Para $aa$, não há regra com corpo $AA$, logo o conjunto é vazio. Para $ab$, a regra $S\to AB$ dá $\{S\}$.

No intervalo $aab$, o corte $a\mid ab$ oferece $(A,S)$, mas não existe regra com corpo $AS$. O corte $aa\mid b$ tem conjunto esquerdo vazio. Portanto, $T[1,3]=\emptyset$ e a palavra é rejeitada. Esta gramática gera os blocos $a^nb^n$ com $n\ge1$, pelo que rejeitar $aab$ concorda com as contagens.

Confere a tua resposta:

*   Na diagonal obtém A, A, B.
*   Só ab tem S entre as células de comprimento dois.
*   Confere os dois cortes de aab sem fabricar B para aa.

Erros frequentes

Não uses A do primeiro a e B do último b ignorando o símbolo intermédio. Não troques C por S só porque C pode derivar SB.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/propriedades-livres/#cyk-decidir-a-perten%C3%A7a)

Intercalação com uma regular

Sejam $L=\{a^nb^n\mid n\ge0\}$ e $R=c^*$. A intercalação preserva a ordem interna de uma palavra de cada linguagem. Decide se $cacb$, $cbca$ e $ccc$ pertencem a $inter(L,R)$. Descreve depois um PDA para esta intercalação e generaliza a construção para qualquer CFL e qualquer regular. Adaptação do exercício 6d da TP de propriedades de CFL.

Pista

Retira os c para testar a ordem e a contagem dos outros símbolos.

Solução

Em $cacb$, retirar os $c$ deixa $ab\in L$, e os $c$ formam uma palavra de $R$, logo aceita. Em $cbca$, sobra $ba\notin L$ e rejeita. $ccc$ intercala $\varepsilon\in L$ com $ccc\in R$, pelo que aceita.

Usa o PDA por estado final de $L$ e o DFA de $R$. Guarda o par $(p,q)$ de estados, com um fundo novo que a simulação da pilha não retira. Cada letra escolhe entre avançar o PDA mantendo $q$, ou avançar o DFA mantendo $p$ e a pilha. As transições vazias do PDA mantêm $q$. No exemplo, os $c$ pertencem ao DFA e os $a,b$ ao PDA; para alfabetos sobrepostos, o não determinismo escolhe a origem.

Aceita com entrada consumida e ambas as componentes finais. O fundo novo permite ler mais letras da regular mesmo depois de a pilha simulada esvaziar. Cada ramo define duas subsequências em ordem; um ramo aceitante dá uma palavra de cada linguagem, e qualquer intercalação válida permite escolher um ramo aceitante.

Confere a tua resposta:

*   Classifiquei cacb, cbca e ccc, incluindo a palavra vazia de L.
*   Mantive a pilha nas letras da regular e um fundo permanente.
*   Justifiquei as duas direções da construção geral.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/propriedades-livres/#intercala%C3%A7%C3%A3o-de-uma-cfl-com-uma-regular)

Uma palavra longa que deixa o adversário bombear

Considera $K=\{a^nb^nz\mid n\ge0,\ z\in\{a,b\}^n\}$ e um comprimento de repetição $p\ge3$. Um colega tenta provar que K não é CFL usando $s=a^pb^{2p}$. O adversário dá $u=a^{p-1}$, $v=a$, $w=\varepsilon$, $x=bb$ e $y=b^{2p-2}$.

Confere se é um corte permitido e calcula a palavra para qualquer expoente i. Esse corte prova que K é CFL? Escolhe depois uma testemunha que permita a contradição e justifica todos os cortes, sem supor que z só contém a. Adaptação da escolha de testemunha da questão 17 do teste de 11/6/2025.

Pista

Na testemunha com três blocos, a primeira mudança para b fixa n. A parte final pode conter b que sobraram, além dos a finais.

Solução

O corte recompõe s, tem $|vwx|=3\le p$ e $|vx|=3>0$. Para i≥0, dá $a^{p-1+i}b^{2(p-1+i)}\in K$, com $n=p-1+i$ e $z=b^n$. Logo esta candidata não força a contradição. Um corte que bombeia uma palavra não demonstra o lema para toda a linguagem, e ainda menos prova que ela seja CFL.

Escolhe $a^{2p}b^{2p}a^{2p}$. Ao retirar v e x, ficam $a^jb^ka^\ell$, todos os blocos não vazios. Se α, β e γ forem as quantidades retiradas dos três blocos, $j=2p-\alpha$, $k=2p-\beta$, $\ell=2p-\gamma$. Pertença a K exigiria $k\ge j$ e $k+\ell=2j$.

A zona de comprimento no máximo p não toca nos dois blocos extremos. Se $\alpha=0$, algum β ou γ é positivo, e $k+\ell<2j$. Se $\alpha>0$, temos γ=0; a igualdade exigiria $\beta=2\alpha$, mas $k\ge j$ exigiria $\beta\le\alpha$, impossível. Portanto i=0 sai de K em qualquer corte. Supondo K CFL, isto contradiz o lema. Podemos exigir p≥3 aumentando o seu comprimento, se necessário.

Confere a tua resposta:

*   Verifiquei que a^p b^(2p) pertence a K e que o corte tem zona de comprimento 3.
*   Obtive a^(p−1+i) b^(2(p−1+i)) para todo i≥0, sem afirmar que K é CFL.
*   Usei a^(2p) b^(2p) a^(2p) e as condições k≥j e k+ℓ=2j para cobrir todos os cortes.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/propriedades-livres/#a-palavra-escolhida-pode-admitir-uma-repeti%C3%A7%C3%A3o)