package Ġcom . bs se 2 0 1 8 . sal av at ov . flt . autom ata Ċ Ċ import Ġcom . bs se 2 0 1 8 . sal av at ov . flt . grammar s . Context Free Grammar . Companion . Epsilon Ċ import Ġorg . junit . jupiter . api . Assertions .* Ċ import Ġorg . junit . jupiter . api . Nested Ċ import Ġorg . junit . jupiter . api . Test Ċ Ċ internal Ġclass ĠPush Down Automaton Test Ġ{ ĊĠĠĠ Ġ@ Nested ĊĠĠĠ Ġinner Ġclass ĠBuild From Strings Ġ{ ĊĠĠĠĠĠĠĠ Ġ@ Test ĊĠĠĠĠĠĠĠ Ġfun Ġ` Full Graph Ġg 1 `() Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrules Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" S Ġa ĠS ", ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" S Ġa " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠPush Down Automaton ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair (" a ", Ġ 2 ), ĠPair (" a ", Ġ 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair (" S ", Ġ 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Of (" S " Ġto Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Of (" S " Ġto ĠlistOf ( 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" S " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp da Ġ= ĠPush Down Automaton . from Strings ( rules ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġp da ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ@ Test ĊĠĠĠĠĠĠĠ Ġfun Ġ` Part Ġof ĠMemory Aliases Ġg 2 `() Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrules Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" V Ġ(( S Ġ| Ġeps ) Ġb )* Ġ( S Ġ| Ġeps )" ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠPush Down Automaton ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair ( Epsilon , Ġ 3 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair (" S ", Ġ 1 ), ĠPair ( Epsilon , Ġ 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair ( Epsilon , Ġ 4 ), ĠPair (" S ", Ġ 5 ), ĠPair ( Epsilon , Ġ 5 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair ( Epsilon , Ġ 2 ), ĠPair ( Epsilon , Ġ 3 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( Pair (" b ", Ġ 4 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Of (" V " Ġto Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Of (" V " Ġto ĠlistOf ( 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" V " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp da Ġ= ĠPush Down Automaton . from Strings ( rules ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġp da ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ@ Test ĊĠĠĠĠĠĠĠ Ġfun Ġ` W or st Ġcase Ġextended Ġgrammar `() Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp da Ġ= ĠPush Down Automaton . from Strings ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (" S Ġa Ġb Ġ| Ġa ĠS Ġb ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠPush Down Automaton ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (" a " Ġto Ġ 2 , Ġ" a " Ġto Ġ 3 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (" b " Ġto Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (" S " Ġto Ġ 4 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf (" b " Ġto Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Of (" S " Ġto Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Of (" S " Ġto ĠlistOf ( 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" S " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġp da ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Nested ĊĠĠĠ Ġinner Ġclass ĠE psilon Pro ducers Ġ{ ĊĠĠĠĠĠĠĠ Ġ@ Test ĊĠĠĠĠĠĠĠ Ġfun Ġ` something Ġ 1 `() Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrules Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" V Ġ(( S Ġ| Ġeps ) Ġb )* Ġ( S Ġ| Ġeps )", ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" S ĠS " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp da Ġ= ĠPush Down Automaton . from Strings ( rules ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( set Of (" V "), Ġp da . epsilon Pro ducers ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ@ Test ĊĠĠĠĠĠĠĠ Ġfun Ġ` eps Ġchain `() Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrules Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" S Ġa Ġ| ĠE 1 ", ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" E 1 Ġb Ġ| ĠE 2 ", ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" E 2 Ġlo l Ġ| Ġeps " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp da Ġ= ĠPush Down Automaton . from Strings ( rules ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( set Of (" S ", Ġ" E 1 ", Ġ" E 2 "), Ġp da . epsilon Pro ducers ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }