A gramática livre de contexto (CFG) para o idioma `aⁿbⁿ`, onde` n ≥ 0`, é:

`` `
S -> ASB | ε
`` `

Explicação:

* s: Este é o símbolo inicial da gramática. Representa uma sequência pertencente ao idioma `aⁿbⁿ`.
* a: Representa o personagem literal 'a'.
* b: Representa o personagem literal 'B'.
* |: Representa "ou". Indica que existem várias regras de produção para o símbolo à esquerda.
* ε: Representa a sequência vazia.

como funciona:

1. `s -> asb`: Essa regra gera um 'a', seguido por um 's' (que acabará por gerar mais 'A e' B's), seguido por A 'B'. Cada vez que essa regra é aplicada, ele efetivamente adiciona um 'a' à esquerda e um 'b' à direita, mantendo o saldo exigido pelo idioma.

2. `s -> ε`: Esta regra fornece o caso base para a recursão. Ele permite que a derivação termine, produzindo a sequência vazia (onde n =0).

Exemplos de derivação:

* n =0:String vazia (ε)
`S -> ε`

* n =1:"ab"
`S -> asb`
`S -> aεb`
`S -> ab`

* n =2:"AABB"
`S -> asb`
`S -> aasbb`
`S -> aaεbb`
`S -> aabb`

* n =3:"aaabbb"
`S -> asb`
`S -> aasbb`
`S -> aaasbbb`
`S -> aaaεbbb`
`S -> aaabbb`

Por que este CFG gera apenas aⁿbⁿ:

A única maneira de derivar uma string de 's' é aplicando repetidamente a regra `s -> asb` zero ou mais vezes, seguida pela aplicação da regra` s -> ε` uma vez. Cada aplicação de `s -> asb` adiciona um 'a' à esquerda e um 'b' à direita. Portanto, a sequência resultante sempre terá um número igual de 'A e' B, com todos os 'A precedindo todos os' B's. Isso descreve com precisão o idioma `aⁿbⁿ`.

Conceitos -chave:

* Gramática sem contexto (CFG): Uma gramática formal, onde as regras de produção têm um único símbolo não terminal no lado esquerdo e qualquer combinação de símbolos terminais e não terminais no lado direito. A aplicação de uma regra de produção não depende do contexto em que o símbolo não terminal aparece.

* Símbolos do terminal: Símbolos que aparecem na sequência final (por exemplo, 'a', 'b').

* símbolos não terminais: Símbolos que representam categorias gramaticais ou etapas intermediárias na derivação (por exemplo, 's').

* Iniciar o símbolo: O símbolo não terminal do qual todas as cordas no idioma são derivadas (por exemplo, 's').

* Regras de produção: Regras que especificam como os símbolos não terminais podem ser substituídos por outros símbolos (por exemplo, `s -> asb`).

Esse CFG é um exemplo clássico frequentemente usado para ilustrar o poder dos CFGs e sua capacidade de expressar idiomas que não são regulares. O idioma `aⁿbⁿ` é um exemplo padrão de um idioma sem contexto que não é um idioma regular.