package Ġorg . prime . util Ċ Ċ import Ġorg . prime . util . machines . Linear Bounded Automaton Ċ import Ġorg . prime . util . machines . T uring Machine Ċ Ċ interface ĠDer ivation Builder Ġ{ ĊĠĠĠ Ġfun Ġbuild Der ivation ( input : ĠList < String >, Ġgrammar : ĠGram mar ): ĠMutable List < String > Ċ } Ċ Ċ /** Ċ Ġ* ĠDer ivation Ġbuilder Ġuses ĠT uring Machine Ġto Ġget Ġaccumulated Ġused Ġdelt as Ġto Ġbuild Ġderiv ations Ċ Ġ*/ Ċ class ĠDer ivation Builder T 0 ( private Ġval Ġt uring Machine : ĠT uring Machine ) Ġ: ĠDer ivation Builder Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġbuild Der ivation ( input : ĠList < String >, Ġgrammar : ĠGram mar ): ĠMutable List < String > Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcurrent Word Ġ= Ġmutable ListOf ( t uring Machine . start State ) ĊĠĠĠĠĠĠĠ Ġval Ġproduction s Ġ= Ġgrammar . production s ĊĠĠĠĠĠĠĠ Ġinput . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Word . add ( get Bracket Symbol ( it , Ġit )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġrepeat ( input . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Word . add ( get Bracket Symbol ( Constants . EPS ILON , Ġ"_ ")) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġrepeat ( input . size Ġ+ Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Word . add ( 0 , Ġget Bracket Symbol ( Constants . EPS ILON , Ġ"_ ")) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġmutable ListOf ( current Word . to Pretty Word ()) ĊĠĠĠĠĠĠĠ Ġfor Ġ( d Ġin Ġt uring Machine . used Del tas ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( p Ġin Ġproduction s . filter Ġ{ Ġp Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . left Symbols . contains ( d . currentState ) Ġ&& Ġp . right Symbols . contains ( d . next State ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprod Result Ġ= Ġp . apply ( current Word )?. to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prod Result Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( prod Result . to Pretty Word ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Word Ġ= Ġprod Result ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġfinish Production s Ġ= Ġproduction s . filter Ġ{ Ġp Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġp . left Symbols . contains ( t uring Machine . accept State ) Ġ&& Ġp . right Symbols . size Ġ!= Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġaccept E ps Ġ= Ġproduction s . find Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . left Symbols . contains ( t uring Machine . accept State ) Ġ&& Ġit . right Symbols . size Ġ== Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} !! ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġchanged Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfinish Production s . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Word Ġ= Ġit . apply ( current Word ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Word Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( new Word . to Pretty Word ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Word Ġ= Ġnew Word . to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġchanged Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! changed ) Ġbreak ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġchanged Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Word Ġ= Ġaccept E ps . apply ( current Word ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Word Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( new Word . to Pretty Word ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Word Ġ= Ġnew Word . to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġchanged Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! changed ) Ġbreak ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Bracket Symbol ( left : ĠString , Ġright : ĠString ) Ġ= Ġ" ($ left |$ right )" ĊĊĠĠĠ Ġprivate Ġfun ĠList < String >. to Pretty Word () Ġ= ĠtoString (). replace ("[ ", Ġ""). replace (" ]", Ġ"") Ċ } ĊĊ Ċ class ĠDer ivation Builder T 1 ( val Ġl ba : ĠLinear Bounded Automaton ) Ġ: ĠDer ivation Builder Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġbuild Der ivation ( input : ĠList < String >, Ġgrammar : ĠGram mar ): ĠMutable List < String > Ġ{ ĊĠĠĠĠĠĠĠ ĠTODO (" Not Ġyet Ġimplemented ") ĊĠĠĠ Ġ} Ċ } ĊĊ