Матрицалық грамматика - Matrix grammar

Бұл мақалада а қолданылған әдебиеттер тізімі, байланысты оқу немесе сыртқы сілтемелер, бірақ оның көздері түсініксіз болып қалады, өйткені ол жетіспейді кірістірілген дәйексөздер. Көмектесіңізші жақсарту осы мақала таныстыру дәлірек дәйексөздер. (Наурыз 2016) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

A матрицалық грамматика Бұл ресми грамматика онда бір туындылардың орнына қойылымдар ақырғы реттікке топтастырылады. Өнімді бөлек қолдануға болмайды, оны дәйектілікпен қолдану керек. Осындай өндірістердің кезектілігін қолданған кезде қайта жазу әрбір өндіріске сәйкес, бірінші, екінші және т.с.с. соңғы өндіріс қайта қолданылғанға дейін орындалады. Бірізділіктер деп аталады матрицалар.

Матрицалық грамматика - кеңейту контекстсіз грамматика, және а-ның бір данасы басқарылатын грамматика.

Ресми анықтама

A матрицалық грамматика бұл төртбұрыш${displaystyle G = (V_ {N}, V_ {T}, X_ {0}, M)}$қайда

• ${displaystyle V_ {N}}$ - терминал емес ақырғы жиынтығы
• ${displaystyle V_ {T}}$ терминалдардың ақырғы жиынтығы болып табылады
• ${displaystyle X_ {0}}$ ерекше элементі болып табылады ${displaystyle V_ {N}}$, яғни. бастапқы белгі
• ${displaystyle M}$ - элементтері реттелген жұптар болатын бос емес тізбектердің ақырлы жиынтығы ${displaystyle (P, Q)}$ қайда

${displaystyle төрт бұрандалы V ^ {*} V_ {N} V ^ {*}, төртінші Qin V ^ {*}, төртінші V = V_ {N} кесе V_ {T}.}$^[1]

Жұптар деп аталады өндірістер, ретінде жазылған ${displaystyle P o Q}$. Бірізділіктер деп аталады матрицалар және ретінде жазылуы мүмкін

${displaystyle m = [P_ {1} o Q_ {1}, ldots, P_ {r} o Q_ {r}].}$

Келіңіздер ${displaystyle F}$ матрицаларда пайда болатын барлық өндірістердің жиынтығы болыңыз ${displaystyle m}$ матрицалық грамматика ${displaystyle G}$. Содан кейін матрицалық грамматика ${displaystyle G}$ типті${displaystyle i, i = 0,1,2,3}$, ұзындық, сызықтық, ${displaystyle lambda}$-Тегін, контекстсіз немесе контекстке сезімтал егер және грамматика болса ғана ${displaystyle G_ {1} = (V_ {N}, V_ {T}, X_ {0}, F)}$ келесі қасиетке ие.

Матрицалық грамматика үшін ${displaystyle G}$, екілік қатынас ${displaystyle Rightarrow _ {G}}$ анықталды; ретінде ұсынылған ${displaystyle Rightarrow}$. Кез келген үшін ${displaystyle P, Qin V ^ {*}}$, ${displaystyle PRightarrow Q}$ егер ол бүтін сан болса және бар болса ғана ұстайды ${displaystyle rgeq 1}$ сөздер сияқты

${displaystyle альфа _ {1} ,, ldots, альфа _ {r + 1}, төртбұрыш P_ {1}, ldots, P_ {r}, төртінші Q_ {1}, ldots, Q_ {r}, төртінші R_ {1} , ldots, R_ {r}, төрттік, R ^ {1}, ldots, R ^ {r}}$

астам V бар және

• ${displaystyle альфа _ {1} = P}$ және ${displaystyle альфа _ {r + 1} = Q}$
• ${displaystyle [P_ {1} o Q_ {1}, ldots, P_ {r} o Q_ {r}]}$ матрицаларының бірі болып табылады ${displaystyle G}$
• ${displaystyle альфа _ {i} = R_ {i} P_ {i} R ^ {i}}$ және ${displaystyle альфа _ {i + 1} = R_ {i} Q_ {i} R ^ {i}}$ барлығына ${displaystyle i}$ осындай ${displaystyle 1leq ileq r.}$

Келіңіздер ${displaystyle Rightarrow ^ {*}}$ қатынастың рефлексивті транзитивті жабылуы болуы ${displaystyle Rightarrow}$. Содан кейін, матрица грамматикасы құрған тіл ${displaystyle G}$ арқылы беріледі

${displaystyle L (G) = {PIN {V_ {T}} ^ {*} | X_ {0} Rightarrow ^ {*} P}.}$

Мысалдар

Матрицалық грамматиканы қарастырыңыз

${displaystyle G = ({S, X, Y}, {a, b, c}, S, M)}$

қайда ${displaystyle M}$ келесі матрицаларды қамтитын жинақ:

${displaystyle m_ {0}: [Sightarrow XY], төртінші m_ {1}: [Xightarrow aXb, Yightarrow cY], m_ quad {2}: [Xightarrow ab, Yightarrow c]}$

Тек матрицалар контекстсіз ережелерін жасаңыз контекстке сезімтал тіл

${displaystyle L = {a ^ {n} b ^ {n} c ^ {n} | ngeq 1}.}$Байланыстырушы сөзі ${displaystyle a ^ {n} b ^ {n} c ^ {n}}$болып табылады${displaystyle Aw (a ^ {n} b ^ {n} c ^ {n}) = m_ {0} m_ {1} ^ {n-2} m_ {2}, барлығы ngeq 2}$ және ${displaystyle Aw (abc) = m_ {0} m_ {2}}$.

Бұл мысалды 8 және 9 беттерден табуға болады ^[1] келесі формада: матрицалық грамматиканы қарастырыңыз

${displaystyle G = ({S, X, Y, Z}, {a, b, c}, S, M)}$

қайда ${displaystyle M}$ келесі матрицаларды қамтитын жинақ:

${displaystyle m_ {0}: [Sightarrow abc], төртінші m_ {1}: [Sightarrow aXbYcZ], mad quad {2}: [Xightarrow aX, Yightarrow bY, Zightarrow cZ], mad m_ {3}: [Sightarrow ab, Тіреу б, Zightarrow с]}$

Тек матрицалар контекст-тұрақты ережелерін қалыптастырыңыз контекстке сезімтал тіл

${displaystyle L = {a ^ {n} b ^ {n} c ^ {n} | ngeq 1}.}$

Байланыстырушы сөзі ${displaystyle a ^ {n} b ^ {n} c ^ {n}}$болып табылады${displaystyle Aw (a ^ {n} b ^ {n} c ^ {n}) = m_ {1} m_ {2} ^ {n-2} m_ {3}, барлығы ngeq 2}$ және ${displaystyle Aw (abc) = m_ {0}}$.

Қасиеттері

Келіңіздер ${displaystyle {ce {MAT ^ {lambda}}}}$ матрицалық грамматикамен шығарылатын тілдер класы болу керек, және MAT өндіретін тілдер класы ${displaystyle lambda}$- ақысыз матрицалық грамматика.

• Маңызды емес, MAT енгізілген ${displaystyle {ce {MAT ^ {lambda}}}}$.
• Барлық контекстсіз тілдер бар MATжәне барлық тілдер ${displaystyle {ce {MAT ^ {lambda}}}}$ болып табылады рекурсивті түрде санауға болады.
• MAT астында жабық одақ, тізбектеу, қиылысу тұрақты тілдермен және ауыстырумен.
• Барлық тілдер MAT өндірілуі мүмкін контекстке қатысты грамматика.
• Контекстке қатысты емес, оған жатпайтын тіл бар ${displaystyle {ce {MAT ^ {lambda}}}}$ ^[2].
• Матрицалық грамматикада бір ғана терминал таңбасы бар әр тіл тұрақты болып табылады.

Ашық мәселелер

Тілдерінің бар-жоғы белгісіз ${displaystyle {ce {MAT ^ {lambda}}}}$ олар жоқ MAT, және ол белгісіз ${displaystyle {ce {MAT ^ {lambda}}}}$ контекстке сезімтал емес тілдерді қамтиды ^[3].

Әдебиеттер тізімі

Сілтемелер

• ^ Ábrahám, S. Тіл теориясының кейбір сұрақтары. Халықаралық есептеуіш лингвистикалық конференция, 1965. 1–11 бб. [4]
• ^ Георге Пюн, Мембраналық есептеу: кіріспе, Springer-Verlag New York, Inc., Secaucus, NJ, АҚШ, 2002. 30-32 бет.