Revisión como estaba o 28 de setembro de 2009 ás 08:21 editar TXiKiBoT (conversa \| contribucións) 140.418 edicións m bot Engadido: no:Formell grammatikk ← Edición máis vella		Revisión como estaba o 7 de febreiro de 2010 ás 21:17 editar desfacer Xqbot (conversa \| contribucións) Bots 77.142 edicións m bot Engadido: ca:Gramàtica formal; cambios estética Edición máis nova →
Liña 2: Unha '''gramática formal''' é un obxecto ou modelo matemático que permite especificar unha linguaxe ou lingua, é dicir, é o conxunto de regras capaces de xerar todalas posibilidades combinatorias desa linguaxe, xa sexa esta unha [[linguaxe formal]] ou unha [[linguaxe natural]]. == Introdución == A expresión «gramática formal» ten dous sentidos: * gramática dunha ''linguaxe formal''. * ''descrición formal'' de parte da gramática dunha linguaxe natural. Cando nos referimos a [[linguaxe natural]] estas regras combinatorias reciben o nome de [[sintaxe]], e son inconscientes. 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: bbbdeccc, de, bdec, ... Estas serían tres posibles realizacións da linguaxe cuxa gramática definimos con dúas regras. Liña 50: En resumo: == Elementos constituíntes == * Unha gramática formal é un modelo matemático composto por unha serie de categorías sintácticas que se combinan entre si por medio dunhas regras sintácticas que definen como se crea unha categoría sintáctica por medio doutras ou símbolos da gramática. * Existe unha única categoría superior que denota cadeas completas e válidas. == Mecanismos de especificación == * Por medio destes elementos constituíntes defínese un mecanismo de especificación consistente en repetir o mecanismo de substitución dunha categoría polos seus constituíntes en función das regras comezando pola categoría superior e finalizando cando a oración xa non contén ningunha categoría. Desta forma, a gramática pode xerar ou producir cada unha das cadeas da linguaxe correspondente e só estas cadeas. == Definición == Unha '''Gramática Formal''' é unha [[Tupla \| cuádrupla]] <math> G = (N, T, P, S) \, </math> onde: * <math> N </math> é un [[alfabeto]] de símbolos non terminais (variables). 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''. == Derivacións == Sexa <math> G = (N,T,P,S) </math> unha gramática, e sexan α, β, δ, φ, ρ, ... palabras de <math> \Sigma^</math> . Entón β '''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> ó peche reflexivo e transitivo de <math> \Rightarrow </math>. É dicir α <math> \Rightarrow^* </math> β denota a unha secuencia de derivacións nun número arbitrario de pasos dende α hasta β. * <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> dícese que x é unha '''sentenza''' * Denomínase '''linguaxe formal xerado por G''' ó conxunto <math> L(G) = \{x \in T^* \| S \Rightarrow^* x \}</math> [[Categoría:~~gramática~~Gramática]] [[bs:Formalna gramatika]] [[ca:Gramàtica formal]] [[cs:Formální gramatika]] [[de:Formale Grammatik]]

Gramática formal: Diferenzas entre revisións