Considere o alfabeto ∑ = {a, b}. Seja a linguagem L1 = {aibj tal que i ≤ j ≤ 2i}. Por exemplo: aabbb ∈ L1 porque 2 ≤ 3 ≤ 4. Determine se a linguag...

A linguagem L1 é livre de contexto. Para provar isso, podemos construir uma gramática livre de contexto (GLC) que gere a linguagem L1. A seguir, apresento uma possível GLC para L1: S → aSbb | ε Explicação da GLC: - A variável inicial S gera a palavra vazia (ε) e/ou uma cadeia que começa com um ou mais "a" seguidos de um ou mais "b", com um número de "b" maior ou igual ao número de "a" e menor ou igual ao dobro do número de "a". - A produção aSbb representa a concatenação de uma cadeia que começa com um "a" (ou mais) e termina com um "b" (ou mais), com uma cadeia que começa com um "a" (ou mais) e termina com um número de "b" maior ou igual ao número de "a" e menor ou igual ao dobro do número de "a". - A produção ε representa a palavra vazia. Assim, a GLC acima gera exatamente a linguagem L1. Como foi possível construir uma GLC para L1, concluímos que L1 é livre de contexto.