Gramática formal: Diferenzas entre revisións
Contido eliminado Contido engadido
m Bot - borrado de comas antes de etcétera [http://academia.gal/dicionario#searchNoun.do?nounTitle=etc%C3%A9tera] |
m Arranxos varios using AWB |
||
Liña 20:
<center>
A → bAc → bbAcc → bbbAccc → bbbdeccc.<br />
</center>
O elemento en maiúsculas é o símbolo inicial. Os elementos en minúsculas son símbolos terminais. As cadeas da lingua son aquelas que só conteñen elementos terminais, por exemplo:
Liña 69:
* Debe cumprirse que <math> N \cap T = \emptyset </math>. denotaremos con <math> \Sigma = N \cup T </math> o alfabeto da gramática.
* <math> S \in N </math> é o símbolo inicial ou [[axioma]] da gramática.
* <math> P \,</math>é o conxunto de regras de produción, da forma <math> P = \,</math> { α → β | α <math> \in \Sigma^* N \Sigma^* </math> β <math> \in \Sigma^* </math> }
É dicir, a cadea α debe conter polo menos unha variable, que pode estar rodeada dun ''contexto''.
Liña 79 ⟶ 78:
* β '''derivase''' de α nun paso de derivación, e denotámolo con α <math> \Rightarrow </math> β se existen dúas cadas <math> \phi_1, \phi_2 \in \Sigma^*</math>, e unha produción δ → ρ tales que α = <math> \phi_1 </math> δ <math> \phi_2 </math>, e β = <math> \phi_1 </math> ρ <math> \phi_2 </math>
* Notamos con <math> \Rightarrow^* </math> o peche reflexivo e transitivo de <math> \Rightarrow </math>. É dicir α <math> \Rightarrow^* </math> β denota unha secuencia de derivacións nun número arbitrario de pasos dende α ata β.
* <math> x \in \Sigma^* </math> é unha '''forma sentencial''' de <math>G</math>, pódese obter a seguinte secuencia de derivacións <math>S \Rightarrow^* x</math> . No caso particular de que <math> x \in T^* </math> dise que x é unha '''sentenza'''
* Denomínase '''linguaxe formal xerado por G''' ó conxunto <math> L(G) = \{x \in T^* | S \Rightarrow^* x \}</math>
| |||