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

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

жүктеу 19,95 Mb.

бет	56/195
Дата	25.05.2018
өлшемі	19,95 Mb.
	#17747
түрі	Конспект

1 ... 52 53 54 55 56 57 58 59 ... 195

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

түріндегі ереже жоюшы ереже деп аталады.

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

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

Жою ережелері бар грамматикалар үшін келесі тұжырымдар дұрыс болады.

Әрбір жою ережесінің құрамында бар

грамматикасы үшін оған эквивалентті

түріндегі қысқартылмайтын

грамматикасын құруға болады.

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

түріндегі ереже мен грамматиканың басқа ережелерінің оң жағының құрамына енетін символы болса, онда бастапқы жаңа

символын енгізіп,

ережесін төмендегі екі жаңа ережемен алмастыру:

және

жүктеу 19,95 Mb.

Достарыңызбен бөлісу:

1 ... 52 53 54 55 56 57 58 59 ... 195