Формална граматика — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 16:
: 2. <math>S \rightarrow ba</math>
тада започињемо са почетним симболом ''S'' и одабирамо правило које ће нам дати жељену ниску. Ако одаберемо прво правило замењујемо ''S'' са ''aSb'' и добијамо ниску ''aSb'' на коју може да се даље примени неко од датих правила. Ако опет применимо прво правило, добијамо ''aаSbb''.
Ово понављамо све док у нисци не буду само завршни симболи, односно ''a'' и ''b''. Уколико одаберемо друго правило - да ''S'' замјенимо са ''ab'', тада ће да се добије ниска ''ааbаbb'' и у њој неће бити нетерминала, па је тиме завршено једно извођење. Ово иѕвођење се записује
<math>S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb</math>. На основу тог претходног процеса извођења закључујемо да је језик ове граматике скуп свих ниски које су облика:
<math>\left \{ba, abab, aababb, aaababbb, ...\right \}</math>.
== Формална дефиниција ==
Класичну формализацију формалних граматика први је предложио Наом Чомски 1950.године. Граматику G чине:
*
* Коначан скуп Σ завршних симбола (још важи да су Σ и N дисјунктни скупови)
*продукције за сваки нетерминални симбол.▼
* Коначан скуп Р правила, и за свако правило важи: <math>(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*} </math>
:где је <math>{}^{*}</math> Клинијева звездица а <math>{}^{\cup}</math> скуповна унија. Дакле, свако извођење пресликава један низ знакова у други, при чему први низ знакова садржи барем један незавршни симбол. У случају да је други низ празан низ, тј. не садржи нити један симбол, онда се пише грчко слово епсилон ''ε''.
Грамтика се формално дефинише као уређена четворка (N, Σ, P, S). Језик формалне граматике G = (N, Σ, P, S) означен са L(G) је дефинисан као скуп свих оних ниски завршних симбола које могу бити генерисане од стартног незавршног симбола S применом правила P граматике G.
'''Терминални симболи''', тзв. „терминали“ или „токени“, су заправо оно што обично називамо речима. Зову се терминали, јер се анализа на њима завршава, тј. не растављају се за потребе анализе.
'''Нетерминални симболи''', тзв. „нетерминали“, су апстрактне ознаке за граматичке конструкције. Они се могу раздвојити анализом у зависности од
'''
'''Стартни симбол''' је нетерминал који представља читав језик генерисан граматиком. Од њега полази анализа. Ако нека реченица може да се редукује у овај нетерминал применом продукција граматике, онда се каже да граматика прихвата ову реченицу, да је написана правилно по датој граматици, или да припада језику којег твори граматика.
== Пример ==
| |||