@@ -1104,3 +1104,48 @@ def is_normal_form(self):
11041104 """
11051105return all (
11061106production .is_normal_form ()for production in self ._productions )
1107+
1108+ def get_prefix_language (self ):
1109+ """
1110+ Generates the prefix language of the CFG, i.e., the language of all prefixes of valid words
1111+ Based on https://cs.uwaterloo.ca/~s4bendav/files/CS360S21Lec10.pdf
1112+ """
1113+ if self .is_empty ():
1114+ return CFG ()
1115+ cfg = self
1116+ if not self .is_normal_form ():
1117+ cfg = cfg .to_normal_form ()
1118+ cfg = cfg .remove_useless_symbols ()
1119+ def to_zero (var :Variable ):
1120+ return Variable ((var .value ,0 ))
1121+ new_variables = list (cfg .variables )+ [to_zero (var )for var in cfg .variables ]
1122+ new_productions = list (cfg .productions )
1123+ for p in cfg .productions :
1124+ if len (p .body )== 1 :
1125+ # the production is of the form X -> c
1126+ new_productions .append (Production (
1127+ to_zero (p .head ),
1128+ p .body
1129+ ))
1130+ new_productions .append (Production (
1131+ to_zero (p .head ),
1132+ [Epsilon ()]
1133+ ))
1134+ else :
1135+ # the production is of the form X -> Y Z
1136+ new_productions .append (Production (
1137+ to_zero (p .head ),
1138+ [p .body [0 ],to_zero (p .body [1 ])]
1139+ ))
1140+ new_productions .append (Production (
1141+ to_zero (p .head ),
1142+ [to_zero (p .body [0 ])]
1143+ ))
1144+ new_productions .append (Production (cfg .start_symbol , [Epsilon ()]))
1145+ new_productions .append (Production (to_zero (cfg .start_symbol ), [Epsilon ()]))
1146+ return CFG (
1147+ variables = set (new_variables ),
1148+ terminals = set (cfg .terminals )| {Epsilon ()},
1149+ productions = new_productions ,
1150+ start_symbol = to_zero (cfg .start_symbol ),
1151+ )