Gramàtica regular

De Viquipèdia
Salta a la navegació Salta a la cerca

En lingüística i informàtica, una gramàtica regular és una gramàtica formal en que pot ser classificada com regular-dreta o regular-esquerra. Cada gramàtica regular defineix un llenguatge regular.[1]

Definició[modifica]

Una gramàtica regular dreta una gramàtica formal (N, Σ, P, S) tal que totes les regles de producció a P son d'alguna de les següents formes:

  1. Aa - on A és un no-terminal a N i a és un terminal a Σ
  2. AaB - on A i B son no-terminal a N i a és a Σ
  3. A → ε - on A és a N i ε denotes la cadena buida (cadena de longitud 0)

Una gramàtica regular esquerra es defineix de la següent forma:

  1. Aa - on A és un no-terminal a N i a és un terminal a Σ
  2. A → Ba - on A i B son no-terminal a N i a és a Σ
  3. A → ε - on A és a N i ε denotes la cadena buida (cadena de longitud 0)

Una gramàtica regular és o bé una gramàtica d'esquerra o bé de dreta.

Si es barregen regles de dretes amb d'esquerres s'obté una gramàtica lineal, però no necessàriament una gramàtica regular.

Referències[modifica]

  1. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.