Conversion d'une spécification de langage en règles de production (je ne sais pas si c'est un CFG ou un CSG)

Question

Je dois écrire une fonction qui vérifie si les chaînes d'entrée sont valides pour une spécification de langue donnée. Je pensais que ce serait un CFG standard -> Chomsky Normal Form, puis CYK parsing, mais l'une des règles dans le langage empêche cela.

Certaines règles sont simples, si nous définissons les bornes {a,b,c,d,e,f,P,Q,R,S}, puis les chaînes valides sont

1) L'une des bornes minuscules dans l'isolement
2) Si « x » est une chaîne valide, est donc Sx

Mais la troisième règle est

3) Si X et y sont des chaînes d'entrée valides, sont donc PXY, QXY, RXY

où {P,Q,R} sont les bornes restantes majuscules et X et Y sont des non-terminaux.

À quoi ressemblerait la règle de production pour cela? Je pensais que ce serait quelque chose comme

XY -> PXY (and QXY, RXY) 

mais il y a deux problèmes avec ceci. La première est que ce n'est pas une règle CFG - est-ce que cela signifie que ce langage définit un CSG à la place?

Et le second est que cela ne fonctionne pas, parce que

XY -> PXY -> PPXY

ne serait pas un message valide dans tous les cas.

Answer 1

Je pense que cette grammaire est sans contexte, à moins que j'interprète mal ce que vous dites.

D'abord, nous allons A le non-terminal qui se développe sur une certaine chaîne valide en utilisant simplement les deux premières règles, nous obtenons

A -> a | b | c | d | e | f 

Maintenant, votre deuxième règle dit que si vous pouvez construire la chaîne ω alors vous pouvez construire S ω. Nous pourrions coder que

A -> SA 

Enfin, vous avez dit que si vous avez deux chaînes X et Y, alors vous pouvez les combiner ensemble comme

PXY 
QXY 
RXY 

Une façon de penser que ce serait pour générer la chaîne P, suivie de deux chaînes valides quelconques (idem pour Q ou R). Ainsi, vous pouvez ajouter les règles

A -> PAA | QAA | RAA 

Cela donne la grammaire finale

A -> a | b | c | d | e | f 
A -> SA 
A -> PAA | QAA | RAA 

Hope this helps!