Next: N-queens Problem Up: An Extendible Regular Expression Previous: Syllabification in Optimality Theory

# Mohri & Sproat Replace Operator

Implementation in FSA5 of the contexted replacement operator of [19].

```
macro(r(R),reverse(marker(1,[sigma*,reverse(R)],[>]))).
macro(f(F),reverse(marker(1,[{sigma,>}*,reverse([ignore(F,{>}),>])],
['<1','<2']))).
macro(l1(L), sloppy_ignore(marker(2,[sigma*,L],'<1'),{'<2':'<2'})).
macro(l2(L),marker(3,[sigma*,L],'<2')).
macro(replace(Phi,Psi), {{sigma,'<2':'<2', > :[]},
['<1':'<1',ignore(Phi,{'<1','<2',> }) x Psi,> :[]]}*).
macro(sigma,? - {'<1','<2',>}).

rx(marker(Type,Expr,C),Fa) :-
fsa_regex:rx(identity(determinize(Expr)),Fa0), mark(Type,C,Fa0,Fa).

mark(1,Ins,Fa0,Fa) :-  %% Ins: symbols to be inserted
fsa_data:start_states(Fa1,Starts),  fsa_data:transitions(Fa1,Trs0),
fsa_data:final_states(Fa1,Fins),    fsa_data:all_states(Fa1,AllSts),
ordsets:ord_subtract(AllSts,Fins,NFins0),
replace_trs_sf(Trs0,Trs1,Fa0),
fsa_data:rename_fa(Sig,Starts,NFins,Trs,[],Fa).

replace_trs_sf([],[],_).
replace_trs_sf([trans(A0,B,C)|T0],[trans(A,B,C)|T],Fa):-
( fsa_data:final_state(Fa,A0) -> A=q(A0) ; A=A0 ),
replace_trs_sf(T0,T,Fa).

mark(2,Del,Fa0,Fa) :-  %% Sym is a symbol to be deleted
fsa_data:copy_fa_except(transitions,Fa1,Fa2,Trs0,Trs),
fsa_data:copy_fa_except(final_states,Fa2,Fa,Fins,AllSts),
fsa_data:all_states(Fa0,AllSts),

mark(3,Del,Fa0,Fa) :- %% Del is a symbol to be deleted
fsa_data:copy_fa_except(transitions,Fa1,Fa2,Trs0,Trs),
fsa_data:copy_fa_except(final_states,Fa2,Fa,Fins,AllSts),
fsa_data:all_states(Fa0,AllSts),
ordsets:ord_subtract(AllSts,Fins,NonFins),