Gramatica

$G = (V, \Sigma, P, S)$

  • Onde V eh um conjunto finito de variaveis..
  • $\Sigma$ eh um conjunto finito de objetos chamados simbolos terminais.
  • $S \in V$ eh um simbolo especial chamado de variavel inicial.
  • P eh um conjunto finito de producoes.

producao

As regra de produção são o coração da gramatica, pois especificam maneiras de transformar uma cadeia em outra, associando uma linguagem a gramatica.

Uma producao altera uma string ou substring, portanto, se a producao eh:

$x -> y$

entao, podemos aplicar a producao x->y em uma string: $w = uxv -> z = uyv$

sendo escrito como $w \implies z$, ou seja, w deriva z, ou z eh derivado de w.

Linguagem gerada por G

$L(G) = \lbrace w \in T^* : S \implies w \rbrace$ // todas as cadeias geradas por G.