Содержание курса


Қысқартылмайтын грамматикалардың түрленуі



бет9/28
Дата06.02.2022
өлшемі2,16 Mb.
#81226
түріКонспект
1   ...   5   6   7   8   9   10   11   12   ...   28
Байланысты:
111 tokkojina m.a. khurast. tilder men avtomattar teoriyasi

2.3 Қысқартылмайтын грамматикалардың түрленуі


түріндегі ереже жоюшы ереже деп аталады.
Ал грамматика қысқартылмайтын немесе жою ережелерінсіз грамматика деп келесі жағдайларда аталады:

  1. егер грамматика кестесінде жою ережелері болмаса

  2. немесе грамматика кестесінде грамматикасының бастауыш символы және оң жағында кездесетін түріндегі бір ғана ереже болса.

Жою ережелері бар грамматикалар үшін келесі тұжырымдар дұрыс болады.
Әрбір жою ережесінің құрамында бар грамматикасы үшін оған эквивалентті түріндегі қысқартылмайтын грамматикасын құруға болады.
Қысқартылмайтын грамматиканы құру жою ережелерінде терминал еместерді шығару нәтижесінде алынған қосымша ережелерді құру жолымен берілген грамматика ережелер санының көбеюін көздейді. Қосымша ережелер құру үшін грамматиканың барлық ережелерінде жою терминал емес символдарды барлық мүмкін бос шынжырлармен алмастыру қажет. Егер грамматикада түріндегі ереже мен грамматиканың басқа ережелерінің оң жағының құрамына енетін символы болса, онда бастапқы жаңа символын енгізіп, ережесін төмендегі екі жаңа ережемен алмастыру: және .




Достарыңызбен бөлісу:
1   ...   5   6   7   8   9   10   11   12   ...   28




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет