Индексирана граматика — разлика између измена
Садржај обрисан Садржај додат
Add 3 books for Википедија:Проверљивост (20210201)) #IABot (v2.0.8) (GreenC bot |
Синтакса – параметар у наводницима. |
||
Ред 7:
У пракси, стекови индекаса могу да броје и памте која правила су примењена којим редоследом. На пример, индексиране граматике могу да опишу овај не-контекстно слободни језик:
:<math> L = \{a^n b^n c^n | n \geq 1 \} </math><ref name="Hopcroft_and_Ullman"> {{Cite book |last=Hopcroft | first = John | last2 = Ullman | first2 = Jeffrey | title = Introduction to automata theory, languages, and computation |url=https://archive.org/details/introductiontoau00hopc_091 |year=1979| publisher = Addison-Wesley |isbn=978-0-201-02988-8|pages=[https://archive.org/details/introductiontoau00hopc_091/page/n397 390]-}}</ref>
следећим скупом правила извођења (-{''f''}- and -{''g''}- су индекси):
Ред 21:
Стек -{''g''}--ова који расте у средини броји колико пута (<math>n-1</math>) је A било замењено једним -{''a''}- и једним -{''c''}-; свако -{''g''}- на крају постаје завршни симбол -{''b''}-.
Проблем одређивања да ли дату ниску препознаје дата индексирана граматика је [[НП-комплетни проблеми|НП-комплетан]].<ref name="Hopcroft_and_Ullman"/>
== Линеарне индексиране граматике ==
|