Матрицалық грамматика – өндіріс ережелері тізбектелген формальды грамматика. Ережелер жеке-жеке емес, тізбек бойынша қолданылады. Грамматика, тіл білімі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Матрицалық грамматика – бұл формальды грамматика, онда жеке өндірістердің орнына өндірістер шекті тізбектерге топтастырылады. Өндіріс жеке қолданылмайды, ол міндетті түрде тізбек бойынша қолданылуы керек. Мұндай өндіріс тізбегін қолдану кезінде, қайта жазу әр өндіріс бойынша реттілікпен, біріншісі, екіншісі, тағы басқалары, соңғы өндіріс қайта жазу үшін қолданылғанша жүзеге асырылады. Бұл тізбектер матрицалар деп аталады. Матрицалық грамматика – контекстсіз грамматиканың кеңейтілген түрі және бақыланатын грамматиканың бір мысалы.
A matrix grammar is a formal grammar in which instead of single productions, productions are grouped together into finite sequences. A production cannot be applied separately, it must be applied in sequence. In the application of such a sequence of productions, the rewriting is done in accordance to each production in sequence, the first one, second one etc. till the last production has been used for rewriting. The sequences are referred to as matrices. Matrix grammar is an extension of context free grammar, and one instance of a controlled grammar.
Қасиеттері
MAT^\lambda – матрицалық грамматикалармен туындайтын тілдер класы, ал MAT – еркін матрицалық грамматикалармен туындайтын тілдер класы. Әрине, MAT, MAT^\lambda-ға кіреді. Барлық контекстсіз тілдер MAT-та, ал MAT^\lambda-дағы барлық тілдер рекурсивті түрде тізімделеді. MAT одақтастыру, қосылу, тұрақты тілдермен қиылысу және өзгеріс бойынша жабық. MAT-тағы барлық тілдер контекстке сезімтал грамматикамен туындатылуы мүмкін. MAT^\lambda-ға жатпайтын контекстке сезімтал тіл бар. Тек бір терминал символы бар матрицалық грамматикамен туындатылған әрбір тіл тұрақты.
Let MAT^\lambda be the class of languages produced by matrix grammars, and MAT the class of languages produced by free matrix grammars. Trivially, MAT is included in MAT^\lambda. All context free languages are in MAT, and all languages in MAT^\lambda are recursively enumerable. MAT is closed under union, concatenation, intersection with regular languages and permutation. All languages in MAT can be produced by a context sensitive grammar. There exists a context sensitive language which does not belong to MAT^\lambda Each language produced by a matrix grammar with only one terminal symbol is regular.
Ашық мәселелер
MAT^\lambda-да MAT-да жоқ тілдердің болуы белгісіз, сондай-ақ MAT^\lambda контекстке сезімтал емес тілдерді қамтиды ма, жоқ па, ол да белгісіз.
It is not known whether there exist languages in MAT^\lambda which are not in MAT, and it is neither known whether MAT^\lambda contains languages which are not context sensitive .
Түсініктемелер
Ábrahám, S. Тіл теориясының кейбір сұрақтары. Есептеу лингвистикасы бойынша халықаралық конференция, 1965. б. 1–11. Георге Пăун, Мембраналық есептеу: кіріспе, Springer Verlag New York, Inc., Secaucus, NJ, АҚШ, 2002. б. 30–32.
Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1–11. Gheorghe Păun, Membrane Computing: An Introduction, Springer Verlag New York, Inc., Secaucus, NJ, USA, 2002. pp 30–32