Movatterモバイル変換

Gramática formal

Ourige: Biquipédia, la anciclopédia lhibre.

Uagramática formal (alguas bezes simplesmente chamada degramática) ye un oubjetomatemático que permite specificar ua lenguaige ó léngua, ó seia, ye un cunjunto deregras de formaçon decadeias nualenguaige formal. Las regras çcriben cumo formar las cadeias de lalfabeto de la lenguaige que son bálidos d'acuordo culasintaxe de la lenguaige. Ua gramática nun çcribe lsseneficados de las cadeias ó l que puode ser feito culhas an qualquiera cuntesto.

La spresson "gramática formal" por tener ls sentidos:

gramática dunlenguaige formal;
çcriçon formal de parte de la gramática dualenguaige natural.

Teorie de la lenguaige formal, la deciplina que studa gramáticas i lenguaiges formales, ye un galho de matemática aplicada. Sues aplicaçones puoden ser ancontradas naciéncia de la cumputaçon teórica,lenguísticas teóricas,semánticas formales,matemática lógica, antre outras árias.

Análeze sintática ye l porcesso de recoincer ua eilocuçon (cadeia anlenguaige natural) quebrando-la nun cunjunto de simblos i analisando cada un cula gramática de la lenguaige. La maiorie de las lenguaiges ténen ls seneficados de sues eilocuçones struturados d'acuordo cula sintaxe — ua prática coincida cumosemántica cumposicional. Cumo resultado, l purmeiro passo para çcrebir l seneficado dua eilocuçon an ema lenguaige ye quebrá-la parte por parte, i mirar la sue forma analisada (coincida cumoarble d'análeze an ciéncia de la cumputaçon, i cumostrutura perfunda angramática geratiba).

Eisemplo antrodutório

[eiditar |eiditar código-fuonte]

Ua gramática cunsiste percipalmente dun cunjunto de regras para cadeias de trasformaçon. (Se elsolo cunsiste dessas regras, el serie unsistema semi-Thue). Para gerar ua cadeia na lenguaige, ampeça-se cun ua cadeia que cunsiste an solo un simblosimblo enicial. Lasregras de porduçon son, anton, aplicadas an qualquiera orde, até qu'ua cadeia que nun cuntenie nin lsimblo enicial, nin ls zeignadossimblos nó-treminales, seia porduzida. La lenguaige formada pula gramática cunsiste de todas las cadeias çtintas que puoden ser geradas dessa forma. Qualquiera sequéncia particular de regras de porduçon subre l simblo enicial porduç ua cadeia çtinta na léngua. Se eisisten bárias maneiras de gerar la mesma sequéncia única, la gramática ye chamada deambígua.Por eisemplo, assumimos que l'alfabeto cunsiste dunla i unb, l simblo enicial yeS, i tenemos las seguintes regras de porduçon:

S\rightarrow aSb

S\rightarrow ba

anton ampeçamos cunS, i podemos scolher ua regra pra aplicar a el. Se nós scolhéssemos la regra 1, oubteríamos la cadeiaaSb. Se nós scolhermos la regra 1 outra beç, nuolo sustituímosS poraSb, i oubtemos la cadeiaaaSbb. Se agora nós scolhermos la regra 2, nós sustituímosS porba i oubtemos la cadeiaaababb, i treminamos. Nós podemos screbir essa série de scolhas mais sucintamente, usando simblos: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ . La lenguaige de la gramática ye anton l cunjunto anfenito $\left\{la^{n}bab^{m}|m\geq 0\right\}=\left\{ba,abab,aababb,aaababbb,...\right\}$ , an quela^k yela repetidok bezes (im, an particular, repersenta l númaro de bezes que la regra de porduçon 1 fui aplicada).

Defeniçon formal

[eiditar |eiditar código-fuonte]

La sintaxe de las gramáticas

[eiditar |eiditar código-fuonte]

Na formalizaçon clássica de las gramáticas geratriç fui purmeiro proposto porNoan Chomsky por buolta de 1956,^[1]^[2] ua gramáticaG cunsiste de ls seguintes cumponentes:

un cunjunto fenitoN desimblos nun treminales, an que nanhun aparece an cadeias formadas a partir deG;
un cunjunto fenito $\Sigma$ desimblos treminales que yeçjunto deN;
un cunjunto fenitoP deregras de porduçon, cun cada regra de la forma

(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}

an que

{*}

ye l'ouperadorstreilha de Klene i

\cup

denotaounion de cunjuntos. Ó seia, cada regra de porduçon mapeia dua cadeia de simblos para outro, an que la purmeira cadeia (la "cabeça" ó "heiad") cuntén un númaro arbitrairo de simblos fornecidos, an que pul menos un deilhes ye un nó-treminal. Ne l causo de la segunda cadeia (l "cuorpo" ó "body") cunsistir solo de lacadeia bazie – i.i., qu'eilha nun cuntenha simblos – eilha puode ser denotada por ua notaçon special (frequentemente

\Lambda

,i ó

\epsilon

) cul antuito d'eibitar cunfuson;

un simblo çtinto $S\in N$ que ye lsimblo enicial.

Eilhas son muitas bezes chamadas desistemas de cadeias reescritos ó degramática de strutura de frases na literatura.^[3]^[4]

La semántica de las gramáticas

[eiditar |eiditar código-fuonte]

L'ouparaçon dua gramática puode ser defenida an tenermos de relaçones an cadeias:

dada ua gramática $G=(N,\Sigma ,P,S)$ , la relaçon binária $\Rightarrow _{G}$ (pronunciada cumo "G deriba nun passo") nas cadeias an $(\Sigma \cup N)^{*}$ ye defenida por:

$x\Rightarrow _{G}y{\mbox{ sse }}\exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)$

la relaçao ${\Rightarrow _{G}}^{*}$ (pronunciada cumoG deriba an zero ó mais passos in zero or more steps) ye defenida cumo lfeixo reflexibo trasitibo de $\Rightarrow _{G}$
uaformula sentencial ye un nembro de $(\Sigma \cup N)^{*}$ que puode ser deribado nun númaro fenito de passos a partir de l simblo enicial $S {\displaystyle S}$ ; ó seia, ua formula sentencial ye un nembro de $\{w\in (\Sigma \cup N)^{*}\mid S{\Rightarrow _{G}}^{*}w\}$ . Ua formula sentencial que nun cuntén nanhun de ls simblos nó treminales (i.i. ye un nembro de $\Sigma ^{*}$ ) ye chamada desentença.^[5]
lalenguaige de $G {\displaystyle G}$ , denotada cumo ${\boldsymbol {L}}(G)$ , ye defenida cumo todas las sentenças que puoden ser deribadas nun númaro fenito de passos a partir de l simblo enicial $S {\displaystyle S}$ ; esto ye, l cunjunto $\{w\in \Sigma ^{*}\mid S{\Rightarrow _{G}}^{*}w\}$ .

Note que la gramática $G=(N,\Sigma ,P,S)$ ye efetibamente unsistema semi-Thue $(N\cup \Sigma ,P)$ , rescrebendo cadeias satamente de l mesmo modo; la única defrença ye que çtinguimossimblos nó-treminales specíficos que percisan ser rescritos an regras, i son ls únicos qu'antressan an rescritas a partir de l simblo enicial $S {\displaystyle S}$ para cadeias sin simblos nó-treminales.

Eisemplo

[eiditar |eiditar código-fuonte]

Para esses eisemplos, lenguaiges formales son specificadas usandonotaçon de custruçon de cunjuntos.

Cunsidre la gramática $G {\displaystyle G}$ an que $N=\left\{S,B\right\}$ , $\Sigma =\left\{la,b,c\right\}$ , $S {\displaystyle S}$ ye l simblo enicial, i $P {\displaystyle P}$ cunsiste de las seguintes regras porduçon:

S\rightarrow aBSc

S\rightarrow abc

Ba\rightarrow aB

Bb\rightarrow bb

Essa gramática define la lenguaige $L(G)=\left\{la^{m}b^{m}c^{m}|m\geq 1\right\}$ an que $la^{m}$ denota la cadeia dem cunsecutibos $l a {\displaystyle la}$ 's. Inda assi, la lenguaige ye l cunjunto de cadeias que cunsisten de 1 ó mais $l a {\displaystyle la}$ 's, seguidos pul mesmo númaro de $b {\displaystyle b}$ 's, seguidos pul mesmo númaro de $c {\displaystyle c}$ 's.

Alguns eisemplos de deribaçon de cadeias an $L(G)$ son:

${\boldsymbol {S}}\Rightarrow _{2}{\boldsymbol {abc}}$
${\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{2}aB{\boldsymbol {abc}}c\Rightarrow _{3}la{\boldsymbol {aB}}bc\Rightarrow _{4}aa{\boldsymbol {bb}}c$
${\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{1}aB{\boldsymbol {aBSc}}c\Rightarrow _{2}aBaB{\boldsymbol {abc}}c\Rightarrow _{3}la{\boldsymbol {aB}}Babcc\Rightarrow _{3}aaB{\boldsymbol {aB}}bcc$ $\Rightarrow _{3}aa{\boldsymbol {aB}}Bbcc\Rightarrow _{4}aaaB{\boldsymbol {bb}}cc\Rightarrow _{4}aaa{\boldsymbol {bb}}bcc$

(Note la notaçon:

P\Rightarrow _{i}Q

lé-se "cadeiaP gera cadeiaQ por meio de la porduçoni", i la parte gerada ye cada beç andicada an negrito)

Gramáticas analíticas

[eiditar |eiditar código-fuonte]

Bisto qu'eisisten ua basto belume dealgoritmos deanáleze sintática, la maiorie desses algoritmos assumen que la lenguaige a ser analisada ye einicialmenteçcrita an meios duagramática formalgeratiba, i l'oubjetibo ye trasformar essa gramática geratiba nun berificador que funcione. Falando mais stritamente, ua gramática geratiba, de modo algun, corresponde al algoritmo ousado para analisar la lenguaige, i bários algoritmos ténen defrentes restriçones na forma an que las regras de porduçon son cunsidradas bien formadas.

Ua abordaige altarnatiba ye formalizar la lenguaige an tenermos dua gramática analítica an purmeiro lugar, que corresponde mais specificamente a l'estrutura i semántica dun berificador para ua lenguaige. Eisemplos de formalismos de gramáticas analíticas ancluen ls seguintes:

la Lenguaige de Máquina amplementa diretamente gramáticas analíticas eirrestritas; sustituiçones de regras son ousadas para trasformar ua antrada para porduzir salidas i cumportamientos; l sistema puode porduzir tamienl diagrama de Ein^{[lhigaçon einatiba]} que mostra l qu'acuntece quando las regras dua gramática analítica eirrestrita stan sendo aplicadas;
Lenguaige d'análeze Top-Down (LATD): un formalismo de gramática analítica altamente menimalista zambolbido recentemente ne ls anhos 70 para studar l cumportamiento de lsberificadores top-down;^[6]
Gramática Eilo: ua forma de gramática analítica zambolbida pa laslenguísticas, que deriban la strutura sintática eisaminando ls relacionamientos posicionales antre dous pares de palabras;^[7]^[8]
Gramáticas d'análeze de spressones (GAEs): son ua generalizaçon mais recente de las LATD zambolbidas an buolta de la prática de laspressebidade percisando de laslenguaiges de porgramaçon i scritores decumpiladors.^[9]

Ber tamien

[eiditar |eiditar código-fuonte]

Refréncias

↑«Thre Models fur the Çcrition of Language».IRE Trasationes on Anformation Theory (2): 113–123. 1956.doi:10.1109/TIT.1956.1056813
↑Syntatic Strutures. The Hague:Mouton. 1957
↑Ginsburg, Seymour (1975).Algebraic and outomata theoretic properties of formal languages. [S.l.]: North-Holland. pp. 8–9.ISBN 0720425069
↑Harrison, Michael La. (1978).Antrodution to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Cumpany. 13 páiginas.ISBN 0201029553
↑Sentential Forms^{[lhigaçon einatiba]}, Cuntext-Fre Grammars, David Matuszek
↑Birman, Alexander,The TMG Recognition Schema, Dotoral thesis, Princeton University, Det. of Eiletrical Anginering, February 1970.
↑Sleator, Daniel D. & Temperly, Daby, "Parsing Anglish with la Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Cumputer Science, 1991.
↑Sleator, Daniel D. & Temperly, Daby, "Parsing Anglish with la Link Grammar,"Third Anternational Workshop on Parsing Technologies, 1993.
↑Ford, Bryan,Packrat Parsing: la Pratical Linear-Eiquipa Algorithn with Backtracking, Master’s thesis, Massachusetts Anstitute of Technology, Set. 2002.

Ligaçones sternas

[eiditar |eiditar código-fuonte]

Yearly Formal Grammar cunference^{[lhigaçon einatiba]}

Teoria de autômatos:linguagem formal egramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Irrestrita	Recursivamente enumerável	Máquina de Turing
--	--	Recursiva	Máquina de Turing que sempre para
Tipo-1	Sensível ao contexto	Sensível ao contexto	Autômato linearmente limitado
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito

Sacado an "https://mwl.wikipedia.org/w/index.php?title=Gramática_formal&oldid=101383"

Catadorie:

Teorie de la cumputaçon

Catadorie scundida:

!Artigos cun lhigaçones einatibas

[8]ページ先頭