Appendice 1: Un'esecuzione di Politically Correct
Per brevita' non viene riportata la conversione da PDA a CFG, in quanto troppo estesa.
Si riferisce allo stesso esempio utilizzato nel capitolo 10.
Initial History:
{Fail[0].Empty |> mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]),
Work[1].Empty |> phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]} Initial Policies:
phi:
Q: [1; 2; 3]
Sigma: [alpha; beta; gamma] Delta (NFA): d(1, alpha) -> (1) d(1, beta) -> (2) d(1, gamma) -> (1) d(2, beta) -> (2) d(2, alpha) -> (1) d(2, gamma) -> (3) d(3, alpha) -> (3) d(3, beta) -> (3) d(3, gamma) -> (3) Q0: 1
Final set status: [1; 2] rho:
Q: [1; 2; 3]
Sigma: [alpha; beta] Delta (NFA): d(1, alpha) -> (1) d(3, alpha) -> (3) d(3, beta) -> (3) d(2, beta) -> (2) d(2, alpha) -> (3) d(1, beta) -> (2) Q0: 1
Final set status: [1; 2]
Check Started!
Creating framed Buchi for Policy phi... Result:
Q: [1; 2; 3; 4; 5]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Delta (NFA): d(1, o-phi) -> (4) d(4, c-phi) -> (1) d(2, o-phi) -> (5) d(5, c-phi) -> (2) d(4, alpha) -> (4) d(4, beta) -> (5) d(4, gamma) -> (4) d(5, beta) -> (5) d(5, alpha) -> (4) d(1, alpha) -> (1) d(1, beta) -> (2) d(1, gamma) -> (1) d(2, beta) -> (2) d(2, alpha) -> (1) d(2, gamma) -> (3) d(3, alpha) -> (3) d(3, beta) -> (3) d(3, gamma) -> (3) Q0: 1
Final set status: [1; 2; 3; 4; 5] done!
Converting NFA in DFA... Resulting DFA:
Q: [1; 2; 3; 4; 5]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Delta (DFA): d(1, alpha) -> (1) d(1, beta) -> (3) d(1, gamma) -> (1) d(1, o-phi) -> (2) d(3, alpha) -> (1) d(3, beta) -> (3) d(3, gamma) -> (5) d(3, o-phi) -> (4) d(5, alpha) -> (5) d(5, beta) -> (5) d(5, gamma) -> (5) d(2, alpha) -> (2) d(2, beta) -> (4) d(2, c-phi) -> (1) d(2, gamma) -> (2) d(4, alpha) -> (2) d(4, beta) -> (4) d(4, c-phi) -> (3) Q0: 1
Final set status: [1; 2; 3; 4; 5] done!
Applying negation to DFA... Result:
Q: [1; 2; 3; 4; 5; 6]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Delta (DFA): d(6, alpha) -> (6) d(6, beta) -> (6) d(6, c-phi) -> (6) d(6, gamma) -> (6) d(6, o-phi) -> (6) d(1, alpha) -> (1) d(2, alpha) -> (2) d(3, alpha) -> (1) d(4, alpha) -> (2) d(5, alpha) -> (5) d(1, beta) -> (3) d(2, beta) -> (4) d(3, beta) -> (3) d(4, beta) -> (4) d(5, beta) -> (5) d(1, c-phi) -> (6) d(2, c-phi) -> (1) d(3, c-phi) -> (6) d(4, c-phi) -> (3) d(5, c-phi) -> (6) d(1, gamma) -> (1) d(2, gamma) -> (2) d(3, gamma) -> (5) d(4, gamma) -> (6) d(5, gamma) -> (5) d(1, o-phi) -> (2) d(2, o-phi) -> (6)
d(3, o-phi) -> (4) d(4, o-phi) -> (6) d(5, o-phi) -> (6) Q0: 1
Final set status: [6] done!
Creating framed Buchi for Policy rho... Result:
Q: [1; 2; 3; 4; 5]
Sigma: [alpha; beta; c-rho; o-rho] Delta (NFA): d(1, o-rho) -> (4) d(4, c-rho) -> (1) d(2, o-rho) -> (5) d(5, c-rho) -> (2) d(4, alpha) -> (4) d(5, beta) -> (5) d(4, beta) -> (5) d(1, alpha) -> (1) d(3, alpha) -> (3) d(3, beta) -> (3) d(2, beta) -> (2) d(2, alpha) -> (3) d(1, beta) -> (2) Q0: 1
Final set status: [1; 2; 3; 4; 5] done!
Converting NFA in DFA... Resulting DFA:
Q: [1; 2; 3; 4; 5]
Sigma: [alpha; beta; c-rho; o-rho] Delta (DFA): d(1, alpha) -> (1) d(1, beta) -> (3) d(1, o-rho) -> (2) d(3, alpha) -> (5) d(3, beta) -> (3) d(3, o-rho) -> (4) d(5, alpha) -> (5) d(5, beta) -> (5) d(2, alpha) -> (2) d(2, beta) -> (4) d(2, c-rho) -> (1) d(4, beta) -> (4) d(4, c-rho) -> (3) Q0: 1
Final set status: [1; 2; 3; 4; 5] done!
Applying negation to DFA... Result:
Q: [1; 2; 3; 4; 5; 6]
Sigma: [alpha; beta; c-rho; o-rho] Delta (DFA): d(6, alpha) -> (6) d(6, beta) -> (6) d(6, c-rho) -> (6) d(6, o-rho) -> (6) d(1, alpha) -> (1) d(2, alpha) -> (2) d(3, alpha) -> (5) d(4, alpha) -> (6) d(5, alpha) -> (5) d(1, beta) -> (3) d(2, beta) -> (4) d(3, beta) -> (3) d(4, beta) -> (4) d(5, beta) -> (5) d(1, c-rho) -> (6) d(2, c-rho) -> (1) d(3, c-rho) -> (6) d(4, c-rho) -> (3) d(5, c-rho) -> (6) d(1, o-rho) -> (2) d(2, o-rho) -> (6) d(3, o-rho) -> (4) d(4, o-rho) -> (6) d(5, o-rho) -> (6) Q0: 1
Final set status: [6] done!
History Linearization... Added Empty Plans:
{Fail[0].Empty |> mu h.(({Empty |> alpha()} + (({Empty |> beta()} ^ {Empty |> h}) ^ {Empty |> h})) + rho[{Empty |> h}]), Work[1].Empty |> phi[(mu
h.(({Empty |> alpha()} + (({Empty |> beta()} ^ {Empty |> h}) ^ {Empty |> h})) + {Empty |> h}) ^ {Empty |> gamma()})]} Before clear:
{Fail[0].((Empty | ((Empty | Empty) | Empty)) | Empty) |> mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]),
Work[1].(((Empty | ((Empty | Empty) | Empty)) | Empty) | Empty) |> phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]}
Linearized History:
{Fail[0].Empty |> mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]),
Work[1].Empty |> phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]} done! Dividing Locations... Resulting Histories: Location -1: mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]) done! Regolarizing history... Signed History: mu h.((alpha + ((beta ^ h1) ^ h2)) + rho[h3]) Regolarized history: mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[mu h.((alpha() + ((beta() ^ h) ^ h)) + h)])
done!
Renaming Variables... Resulting history:
rho[mu B.((alpha() + ((beta() ^ B) ^ B)) + B)])
done!
Converting History Expression into BPA process...
Resulting BPA: A
A:
((alpha + ((beta ^ A) ^ A)) + ((o-rho ^ B) ^ c-rho))
B:
((alpha + ((beta ^ B) ^ B)) + B) done!
Converting BPA process into CFG grammar (CNF)...
T set: [alpha; beta; c-rho; o-rho] NT set: [A; B] Resulting Grammar: NT: [A; B; C; D; E; F; G; H; I; J; K; L; M; N; O; P; Q; R; S; T; U; V; W] T:
[alpha; beta; c-rho; o-rho] PROD: A-> L A-> M B-> D B-> E C-> A D-> F D-> G E-> B F-> alpha G-> H^I H-> J^K I-> B J-> beta K-> B L-> R L-> S M-> N^O N-> P^Q O-> c-rho P-> o-rho Q-> B R-> alpha S-> T^U T-> V^W U-> A V-> beta W-> A S :C done!
Clearing Grammar...Useful prods: A-> L A-> M B-> D B-> E C-> A D-> F D-> G E-> B F-> alpha G-> H^I H-> J^K I-> B J-> beta K-> B L-> R L-> S M-> N^O N-> P^Q O-> c-rho P-> o-rho Q-> B R-> alpha S-> T^U T-> V^W U-> A V-> beta W-> A Nullable symbols:
[]Removed Epsilon productions: A-> L A-> M B-> D B-> E C-> A D-> F D-> G E-> B F-> alpha G-> H^I H-> J^K I-> B J-> beta K-> B L-> R L-> S M-> N^O N-> P^Q O-> c-rho P-> o-rho Q-> B R-> alpha S-> T^U T-> V^W U-> A V-> beta W-> A
Non unit productions: F-> alpha G-> H^I H-> J^K J-> beta M-> N^O N-> P^Q O-> c-rho P-> o-rho R-> alpha S-> T^U
T-> V^W V-> beta
Removed unit prod: NT:
[A; B; C; D; E; F; G; H; I; J; K; L; M; N; O; P; Q; R; S; T; U; V; W]
T:
[alpha; beta; c-rho; o-rho] PROD: A-> N^O A-> T^U A-> alpha B-> H^I B-> alpha C-> N^O C-> T^U C-> alpha D-> H^I D-> alpha E-> H^I E-> alpha F-> alpha G-> H^I H-> J^K I-> H^I I-> alpha J-> beta K-> H^I K-> alpha L-> T^U L-> alpha M-> N^O N-> P^Q O-> c-rho P-> o-rho Q-> H^I Q-> alpha R-> alpha S-> T^U T-> V^W U-> N^O U-> T^U U-> alpha V-> beta W-> N^O W-> T^U W-> alpha S :C Pruned Unused: NT: [C; H; I; J; K; N; O; P; Q; T; U; V; W] T:
[alpha; beta; c-rho; o-rho] PROD: C-> N^O C-> T^U C-> alpha H-> J^K I-> H^I I-> alpha J-> beta K-> H^I K-> alpha N-> P^Q O-> c-rho P-> o-rho Q-> H^I Q-> alpha T-> V^W U-> N^O U-> T^U U-> alpha V-> beta W-> N^O W-> T^U W-> alpha S :C
Merged Equal productions: NT:
[H; N; O; P; Q; T; V; W] T:
[alpha; beta; c-rho; o-rho] PROD: H-> V^Q N-> P^Q O-> c-rho P-> o-rho Q-> H^Q Q-> alpha T-> V^W V-> beta W-> N^O W-> T^W W-> alpha S :W done!
Converting Grammar in Chomsky Normal Form...
Result: NT:
[H; N; O; P; Q; T; V; W] T:
[alpha; beta; c-rho; o-rho] PROD: H-> V^Q N-> P^Q O-> c-rho P-> o-rho Q-> H^Q Q-> alpha T-> V^W V-> beta W-> N^O W-> T^W W-> alpha S :W done!
Converting Grammar in Greibach Normal Form...H-> V^Q
N-> P^Q O-> c-rho P-> o-rho Q-> V^Q^Q Q-> alpha T-> V^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O Step 2: H-> beta^Q N-> o-rho^Q O-> c-rho P-> o-rho Q-> alpha Q-> beta^Q^Q T-> beta^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O Step 3: H-> beta^Q N-> o-rho^Q O-> c-rho P-> o-rho Q-> alpha Q-> beta^Q^Q T-> beta^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O done!
Clearing Grammar...Useful prods: H-> beta^Q N-> o-rho^Q O-> c-rho P-> o-rho Q-> alpha Q-> beta^Q^Q T-> beta^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O Nullable symbols:
[]Removed Epsilon productions: H-> beta^Q N-> o-rho^Q O-> c-rho P-> o-rho Q-> alpha Q-> beta^Q^Q T-> beta^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O
Non unit productions: H-> beta^Q N-> o-rho^Q O-> c-rho P-> o-rho Q-> alpha Q-> beta^Q^Q T-> beta^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O Removed unit prod: NT:
[H; N; O; P; Q; T; V; W] T:
[alpha; beta; c-rho; o-rho] PROD: H-> beta^Q N-> o-rho^Q O-> c-rho P-> o-rho Q-> alpha Q-> beta^Q^Q T-> beta^W V-> beta W-> alpha W-> beta^W^W W-> o-rho^Q^O S :W Pruned Unused: NT: [O; Q; W] T:
[alpha; beta; c-rho; o-rho] PROD: O-> c-rho Q-> alpha Q-> beta^Q^Q W-> alpha W-> beta^W^W W-> o-rho^Q^O S :W
Merged Equal productions: NT:
[O; Q; W] T:
[alpha; beta; c-rho; o-rho] PROD: O-> c-rho Q-> alpha Q-> beta^Q^Q W-> alpha W-> beta^W^W W-> o-rho^Q^O S :W done!
Converting CFG into PDA... Generated PDA:
Q: [0]
Sigma: [alpha; beta; c-rho; o-rho] Stack: [O; Q; W] Delta: d(0, c-rho, O) -> (0, []) d(0, alpha, Q) -> (0, []) d(0, beta, Q) -> (0, [Q; Q]) d(0, alpha, W) -> (0, []) d(0, beta, W) -> (0, [W; W]) d(0, o-rho, W) -> (0, [Q; O]) Q0: 0 Z0: W
Final set status: [] done!
Converting PDA (acceptance by Empty Stack) in PDA (acceptance by Final Status)...
Initial PDA: Q: [0]
Sigma: [alpha; beta; c-rho; o-rho] Stack: [O; Q; W] Delta: d(0, c-rho, O) -> (0, []) d(0, alpha, Q) -> (0, []) d(0, beta, Q) -> (0, [Q; Q]) d(0, alpha, W) -> (0, []) d(0, beta, W) -> (0, [W; W]) d(0, o-rho, W) -> (0, [Q; O]) Q0: 0 Z0: W
Final set status: []
Resulting PDA: Q: [0; 1; 2]
Sigma: [; alpha; beta; c-rho; o-rho] Stack: [!inital!; O; Q; W] Delta: d(1, , !inital!) -> (0, [W; !inital!]) d(0, c-rho, O) -> (0, []) d(0, alpha, Q) -> (0, []) d(0, beta, Q) -> (0, [Q; Q]) d(0, alpha, W) -> (0, []) d(0, beta, W) -> (0, [W; W]) d(0, o-rho, W) -> (0, [Q; O]) d(0, , !inital!) -> (2, []) Q0: 1 Z0: !inital!
Final set status: [2] done!
Applying conjunction between DFA and PDA...
Extended DFA:
Q: [1; 2; 3; 4; 5; 6]
Sigma: [; alpha; beta; c-rho; o-rho] Delta (DFA): d(6, alpha) -> (6) d(6, beta) -> (6) d(6, c-rho) -> (6) d(6, o-rho) -> (6) d(1, alpha) -> (1) d(2, alpha) -> (2) d(3, alpha) -> (5) d(4, alpha) -> (6) d(5, alpha) -> (5) d(1, beta) -> (3) d(2, beta) -> (4) d(3, beta) -> (3) d(4, beta) -> (4) d(5, beta) -> (5) d(1, c-rho) -> (6) d(2, c-rho) -> (1) d(3, c-rho) -> (6) d(4, c-rho) -> (3) d(5, c-rho) -> (6) d(1, o-rho) -> (2) d(2, o-rho) -> (6) d(3, o-rho) -> (4) d(4, o-rho) -> (6) d(5, o-rho) -> (6) d(1, ) -> (1) d(2, ) -> (2) d(3, ) -> (3) d(4, ) -> (4) d(5, ) -> (5) d(6, ) -> (6) Q0: 1
Final set status: [6]
Status Table (DFA,PDA)->Conj : (1,0)->1 (1,1)->2 (1,2)->3 (2,0)->4 (2,1)->5 (2,2)->6 (3,0)->7 (3,1)->8 (3,2)->9 (4,0)->10 (4,1)->11 (4,2)->12 (5,0)->13 (5,1)->14 (5,2)->15 (6,0)->16 (6,1)->17 (6,2)->18 Result: Q: [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18]
Sigma: [; alpha; beta; c-rho; o-rho] Stack: [!inital!; O; Q; W] Delta: d(1, , !inital!) -> (3, []) d(1, alpha, Q) -> (1, []) d(1, alpha, W) -> (1, []) d(1, beta, Q) -> (7, [Q; Q]) d(1, beta, W) -> (7, [W; W]) d(1, c-rho, O) -> (16, []) d(1, o-rho, W) -> (4, [Q; O]) d(2, , !inital!) -> (1, [W; !inital!]) d(4, , !inital!) -> (6, []) d(4, alpha, Q) -> (4, []) d(4, alpha, W) -> (4, [])
d(4, beta, Q) -> (10, [Q; Q]) d(4, beta, W) -> (10, [W; W]) d(4, c-rho, O) -> (1, []) d(4, o-rho, W) -> (16, [Q; O]) d(5, , !inital!) -> (4, [W; !inital!]) d(7, , !inital!) -> (9, []) d(7, alpha, Q) -> (13, []) d(7, alpha, W) -> (13, []) d(7, beta, Q) -> (7, [Q; Q]) d(7, beta, W) -> (7, [W; W]) d(7, c-rho, O) -> (16, []) d(7, o-rho, W) -> (10, [Q; O]) d(8, , !inital!) -> (7, [W; !inital!]) d(10, , !inital!) -> (12, []) d(10, alpha, Q) -> (16, []) d(10, alpha, W) -> (16, []) d(10, beta, Q) -> (10, [Q; Q]) d(10, beta, W) -> (10, [W; W]) d(10, c-rho, O) -> (7, []) d(10, o-rho, W) -> (16, [Q; O]) d(11, , !inital!) -> (10, [W; !inital!]) d(13, , !inital!) -> (15, []) d(13, alpha, Q) -> (13, []) d(13, alpha, W) -> (13, []) d(13, beta, Q) -> (13, [Q; Q]) d(13, beta, W) -> (13, [W; W]) d(13, c-rho, O) -> (16, []) d(13, o-rho, W) -> (16, [Q; O]) d(14, , !inital!) -> (13, [W; !inital!]) d(16, , !inital!) -> (18, []) d(16, alpha, Q) -> (16, []) d(16, alpha, W) -> (16, []) d(16, beta, Q) -> (16, [Q; Q]) d(16, beta, W) -> (16, [W; W]) d(16, c-rho, O) -> (16, []) d(16, o-rho, W) -> (16, [Q; O]) d(17, , !inital!) -> (16, [W; !inital!]) Q0: 2 Z0: !inital!
Final set status: [18] done!
Converting PDA into CFG...done! Clearing Grammar...Useful prods: A-> WO^V AMB-> D^B AOF-> H^F AUG-> UQ^R AUM-> L^R AUR-> T^R AWJ-> WR^V AWM-> NH^V AWP-> P^V AWS-> WY^V AWU-> X^V B-> EPSILON C-> alpha D-> alpha D-> o-rho^G^I E-> c-rho F-> EPSILON G-> alpha H-> alpha I-> c-rho IK-> beta^K^T J-> EPSILON K-> alpha K-> beta^K^T KL-> beta^O^W L-> alpha L-> beta^L^T M-> c-rho N-> EPSILON NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W P-> alpha P-> beta^P^X P-> o-rho^W^Y Q-> c-rho R-> EPSILON S-> A T-> alpha T-> beta^T^T U-> c-rho UQ-> beta^L^T V-> EPSILON W-> alpha W-> beta^W^W WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WR-> beta^P^X WR-> o-rho^W^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y Y-> c-rho Nullable symbols: [B; F; J; N; R; V]Removed Epsilon productions: A-> WO A-> WO^V AMB-> D AMB-> D^B AOF-> H AOF-> H^F AUG-> UQ AUG-> UQ^R AUM-> L AUM-> L^R AUR-> T AUR-> T^R AWJ-> WR AWJ-> WR^V AWM-> NH AWM-> NH^V AWP-> P AWP-> P^V AWS-> WY AWS-> WY^V AWU-> X
AWU-> X^V C-> alpha D-> alpha D-> o-rho^G^I E-> c-rho G-> alpha H-> alpha I-> c-rho IK-> beta^K^T K-> alpha K-> beta^K^T KL-> beta^O^W L-> alpha L-> beta^L^T M-> c-rho NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W P-> alpha P-> beta^P^X P-> o-rho^W^Y Q-> c-rho S-> A T-> alpha T-> beta^T^T U-> c-rho UQ-> beta^L^T W-> alpha W-> beta^W^W WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WR-> beta^P^X WR-> o-rho^W^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y Y-> c-rho
Non unit productions: A-> WO^V AMB-> D^B AOF-> H^F AUG-> UQ^R AUM-> L^R AUR-> T^R AWJ-> WR^V AWM-> NH^V AWP-> P^V AWS-> WY^V AWU-> X^V C-> alpha D-> alpha D-> o-rho^G^I E-> c-rho G-> alpha H-> alpha I-> c-rho IK-> beta^K^T K-> alpha K-> beta^K^T KL-> beta^O^W L-> alpha L-> beta^L^T M-> c-rho NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W P-> alpha P-> beta^P^X P-> o-rho^W^Y Q-> c-rho T-> alpha T-> beta^T^T U-> c-rho UQ-> beta^L^T W-> alpha W-> beta^W^W WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WR-> beta^P^X WR-> o-rho^W^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y Y-> c-rho
Removed unit prod: NT:
[A; AMB; AOF; AUG; AUM; AUR; AWJ; AWM; AWP; AWS; AWU; C; D; E; G; H; I; IK; K; KL; L; M; NH; O; P; Q; S; T; U; UQ; W; WO; WR; WY; X; Y]
T:
[; alpha; beta; c-rho; o-rho] PROD: A-> WO^V A-> beta^L^WY A-> beta^NH^X A-> o-rho^KL^Y AMB-> D^B AMB-> alpha AMB-> o-rho^G^I AOF-> H^F AOF-> alpha AUG-> UQ^R AUG-> beta^L^T AUM-> L^R AUM-> alpha AUM-> beta^L^T AUR-> T^R AUR-> alpha AUR-> beta^T^T AWJ-> WR^V AWJ-> beta^P^X AWJ-> o-rho^W^Y AWM-> NH^V AWM-> beta^L^WY
AWM-> beta^NH^X AWM-> o-rho^O^Y AWP-> P^V AWP-> alpha AWP-> beta^P^X AWP-> o-rho^W^Y AWS-> WY^V AWS-> beta^T^WY AWS-> beta^WY^X AWS-> o-rho^W^Y AWU-> X^V AWU-> alpha AWU-> beta^X^X AWU-> o-rho^W^Y C-> alpha D-> alpha D-> o-rho^G^I E-> c-rho G-> alpha H-> alpha I-> c-rho IK-> beta^K^T K-> alpha K-> beta^K^T KL-> beta^O^W L-> alpha L-> beta^L^T M-> c-rho NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W P-> alpha P-> beta^P^X P-> o-rho^W^Y Q-> c-rho S-> WO^V S-> beta^L^WY S-> beta^NH^X S-> o-rho^KL^Y T-> alpha T-> beta^T^T U-> c-rho UQ-> beta^L^T W-> alpha W-> beta^W^W WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WR-> beta^P^X WR-> o-rho^W^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y Y-> c-rho S :S Pruned Unused: NT: [KL; L; NH; O; S; T; V; W; WO; WY; X; Y] T:
[; alpha; beta; c-rho; o-rho] PROD: KL-> beta^O^W L-> alpha L-> beta^L^T NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W S-> WO^V S-> beta^L^WY S-> beta^NH^X S-> o-rho^KL^Y T-> alpha T-> beta^T^T W-> alpha W-> beta^W^W WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y Y-> c-rho S :S
Merged Equal productions: NT:
[KL; L; NH; O; S; T; V; W; WO; WY; X; Y] T:
[; alpha; beta; c-rho; o-rho] PROD: KL-> beta^O^W L-> alpha L-> beta^L^T NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W S-> WO^V S-> beta^L^WY S-> beta^NH^X S-> o-rho^KL^Y T-> alpha T-> beta^T^T W-> alpha W-> beta^W^W WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y
Y-> c-rho S :S done!
Checking for useful symbols... Initial New V: [L; O; T; W; X; Y] Initial Old V: [] New V: [KL; L; NH; O; T; W; WY; X; Y] Old V: [L; O; T; W; X; Y] New V: [KL; L; NH; O; S; T; W; WO; WY; X; Y] Old V: [KL; L; NH; O; T; W; WY; X; Y] New V: [KL; L; NH; O; S; T; W; WO; WY; X; Y] Old V: [KL; L; NH; O; S; T; W; WO; WY; X; Y] Final set: [KL; L; NH; O; S; T; W; WO; WY; X; Y]
The Grammar is Empty: false
Plan (Fail[0].Empty) doesn't respect rho at location -1.A possible violation is: beta^alpha^o-rho^alpha^c-rho
Dividing Locations... Resulting Histories: Location -1:
phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]
done!
Regolarizing history... Signed History:
phi[(mu h.((alpha + ((beta ^ h1) ^ h2)) + h3) ^ gamma)]
Regolarized history:
phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]
done!
Renaming Variables... Resulting history:
phi[(mu A.((alpha() + ((beta() ^ A) ^ A)) + A) ^ gamma())]
done!
Converting History Expression into BPA process...
Resulting BPA:
((o-phi ^ (A ^ gamma)) ^ c-phi) A:
((alpha + ((beta ^ A) ^ A)) + A) done!
Converting BPA process into CFG grammar
(CNF)...
T set: [alpha; beta; c-phi; gamma; o-phi] NT set: [A] Resulting Grammar: NT: [A; B; C; D; E; F; G; H; I; J; K; L; M; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: A-> C A-> D B-> K^L C-> E C-> F D-> A E-> alpha F-> G^H G-> I^J H-> A I-> beta J-> A K-> M^N L-> c-phi M-> o-phi N-> O^P O-> A P-> gamma S :B done!
Clearing Grammar...Useful prods: A-> C A-> D B-> K^L C-> E C-> F D-> A E-> alpha F-> G^H G-> I^J H-> A I-> beta J-> A K-> M^N L-> c-phi M-> o-phi N-> O^P O-> A P-> gamma Nullable symbols:
[]Removed Epsilon productions: A-> C A-> D B-> K^L C-> E C-> F D-> A E-> alpha F-> G^H G-> I^J
H-> A I-> beta J-> A K-> M^N L-> c-phi M-> o-phi N-> O^P O-> A P-> gamma
Non unit productions: B-> K^L E-> alpha F-> G^H G-> I^J I-> beta K-> M^N L-> c-phi M-> o-phi N-> O^P P-> gamma
Removed unit prod: NT:
[A; B; C; D; E; F; G; H; I; J; K; L; M; N; O; P]
T:
[alpha; beta; c-phi; gamma; o-phi] PROD: A-> G^H A-> alpha B-> K^L C-> G^H C-> alpha D-> G^H D-> alpha E-> alpha F-> G^H G-> I^J H-> G^H H-> alpha I-> beta J-> G^H J-> alpha K-> M^N L-> c-phi M-> o-phi N-> O^P O-> G^H O-> alpha P-> gamma S :B Pruned Unused: NT: [B; G; H; I; J; K; L; M; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: B-> K^L G-> I^J H-> G^H H-> alpha I-> beta J-> G^H J-> alpha K-> M^N L-> c-phi M-> o-phi N-> O^P O-> G^H O-> alpha P-> gamma S :B
Merged Equal productions: NT:
[B; G; I; K; L; M; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: B-> K^L G-> I^O I-> beta K-> M^N L-> c-phi M-> o-phi N-> O^P O-> G^O O-> alpha P-> gamma S :B done!
Converting Grammar in Chomsky Normal Form...
Result: NT:
[B; G; I; K; L; M; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: B-> K^L G-> I^O I-> beta K-> M^N L-> c-phi M-> o-phi N-> O^P O-> G^O O-> alpha P-> gamma S :B done!
Converting Grammar in Greibach Normal Form...B-> K^L G-> I^O I-> beta K-> M^N L-> c-phi M-> o-phi N-> O^P O-> alpha O-> beta^O^O
P-> gamma Step 2: B-> o-phi^N^L G-> beta^O I-> beta K-> o-phi^N L-> c-phi M-> o-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma Step 3: B-> o-phi^N^L G-> beta^O I-> beta K-> o-phi^N L-> c-phi M-> o-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma done!
Clearing Grammar...Useful prods: B-> o-phi^N^L G-> beta^O I-> beta K-> o-phi^N L-> c-phi M-> o-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma Nullable symbols:
[]Removed Epsilon productions: B-> o-phi^N^L G-> beta^O I-> beta K-> o-phi^N L-> c-phi M-> o-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma
Non unit productions: B-> o-phi^N^L G-> beta^O I-> beta K-> o-phi^N L-> c-phi M-> o-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma
Removed unit prod: NT:
[B; G; I; K; L; M; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: B-> o-phi^N^L G-> beta^O I-> beta K-> o-phi^N L-> c-phi M-> o-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma S :B Pruned Unused: NT: [B; L; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: B-> o-phi^N^L L-> c-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma S :B
Merged Equal productions: NT:
[B; L; N; O; P] T:
[alpha; beta; c-phi; gamma; o-phi] PROD: B-> o-phi^N^L L-> c-phi N-> alpha^P N-> beta^O^O^P O-> alpha O-> beta^O^O P-> gamma S :B done!
Converting CFG into PDA... Generated PDA:
Q: [0]
Sigma: [alpha; beta; c-phi; gamma; o-phi]
Delta: d(0, o-phi, B) -> (0, [N; L]) d(0, c-phi, L) -> (0, []) d(0, alpha, N) -> (0, [P]) d(0, beta, N) -> (0, [O; O; P]) d(0, alpha, O) -> (0, [])
d(0, beta, O) -> (0, [O; O]) d(0, gamma, P) -> (0, []) Q0: 0
Z0: B
Final set status: [] done!
Converting PDA (acceptance by Empty Stack) in PDA (acceptance by Final Status)...
Initial PDA: Q: [0]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Stack: [B; L; N; O; P] Delta: d(0, o-phi, B) -> (0, [N; L]) d(0, c-phi, L) -> (0, []) d(0, alpha, N) -> (0, [P]) d(0, beta, N) -> (0, [O; O; P]) d(0, alpha, O) -> (0, [])
d(0, beta, O) -> (0, [O; O]) d(0, gamma, P) -> (0, []) Q0: 0
Z0: B
Final set status: []
Resulting PDA: Q: [0; 1; 2]
Sigma: [; alpha; beta; c-phi; gamma; o-phi] Stack: [!inital!; B; L; N; O; P] Delta: d(1, , !inital!) -> (0, [B; !inital!]) d(0, o-phi, B) -> (0, [N; L]) d(0, c-phi, L) -> (0, []) d(0, alpha, N) -> (0, [P]) d(0, beta, N) -> (0, [O; O; P]) d(0, alpha, O) -> (0, [])
d(0, beta, O) -> (0, [O; O]) d(0, gamma, P) -> (0, []) d(0, , !inital!) -> (2, []) Q0: 1
Z0: !inital!
Final set status: [2] done!
Applying conjunction between DFA and PDA...
Extended DFA:
Q: [1; 2; 3; 4; 5; 6]
Sigma: [; alpha; beta; c-phi; gamma; o-phi] Delta (DFA): d(6, alpha) -> (6) d(6, beta) -> (6) d(6, c-phi) -> (6) d(6, gamma) -> (6) d(6, o-phi) -> (6) d(1, alpha) -> (1) d(2, alpha) -> (2) d(3, alpha) -> (1) d(4, alpha) -> (2) d(5, alpha) -> (5) d(1, beta) -> (3) d(2, beta) -> (4) d(3, beta) -> (3) d(4, beta) -> (4) d(5, beta) -> (5) d(1, c-phi) -> (6) d(2, c-phi) -> (1) d(3, c-phi) -> (6) d(4, c-phi) -> (3) d(5, c-phi) -> (6) d(1, gamma) -> (1) d(2, gamma) -> (2) d(3, gamma) -> (5) d(4, gamma) -> (6) d(5, gamma) -> (5) d(1, o-phi) -> (2) d(2, o-phi) -> (6) d(3, o-phi) -> (4) d(4, o-phi) -> (6) d(5, o-phi) -> (6) d(1, ) -> (1) d(2, ) -> (2) d(3, ) -> (3) d(4, ) -> (4) d(5, ) -> (5) d(6, ) -> (6) Q0: 1
Final set status: [6]
Status Table (DFA,PDA)->Conj : (1,0)->1 (1,1)->2 (1,2)->3 (2,0)->4 (2,1)->5 (2,2)->6 (3,0)->7 (3,1)->8 (3,2)->9 (4,0)->10 (4,1)->11 (4,2)->12 (5,0)->13 (5,1)->14 (5,2)->15 (6,0)->16 (6,1)->17 (6,2)->18 Result: Q: [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18]
Sigma: [; alpha; beta; c-phi; gamma; o-phi] Stack: [!inital!; B; L; N; O; P] Delta: d(1, , !inital!) -> (3, []) d(1, alpha, N) -> (1, [P]) d(1, alpha, O) -> (1, []) d(1, beta, N) -> (7, [O; O; P])
d(1, beta, O) -> (7, [O; O]) d(1, c-phi, L) -> (16, []) d(1, gamma, P) -> (1, []) d(1, o-phi, B) -> (4, [N; L]) d(2, , !inital!) -> (1, [B; !inital!]) d(4, , !inital!) -> (6, []) d(4, alpha, N) -> (4, [P]) d(4, alpha, O) -> (4, []) d(4, beta, N) -> (10, [O; O; P]) d(4, beta, O) -> (10, [O; O]) d(4, c-phi, L) -> (1, []) d(4, gamma, P) -> (4, []) d(4, o-phi, B) -> (16, [N; L]) d(5, , !inital!) -> (4, [B; !inital!]) d(7, , !inital!) -> (9, []) d(7, alpha, N) -> (1, [P]) d(7, alpha, O) -> (1, []) d(7, beta, N) -> (7, [O; O; P]) d(7, beta, O) -> (7, [O; O]) d(7, c-phi, L) -> (16, []) d(7, gamma, P) -> (13, []) d(7, o-phi, B) -> (10, [N; L]) d(8, , !inital!) -> (7, [B; !inital!]) d(10, , !inital!) -> (12, []) d(10, alpha, N) -> (4, [P]) d(10, alpha, O) -> (4, []) d(10, beta, N) -> (10, [O; O; P]) d(10, beta, O) -> (10, [O; O]) d(10, c-phi, L) -> (7, []) d(10, gamma, P) -> (16, []) d(10, o-phi, B) -> (16, [N; L]) d(11, , !inital!) -> (10, [B; !inital!]) d(13, , !inital!) -> (15, []) d(13, alpha, N) -> (13, [P]) d(13, alpha, O) -> (13, []) d(13, beta, N) -> (13, [O; O; P]) d(13, beta, O) -> (13, [O; O]) d(13, c-phi, L) -> (16, []) d(13, gamma, P) -> (13, []) d(13, o-phi, B) -> (16, [N; L]) d(14, , !inital!) -> (13, [B; !inital!]) d(16, , !inital!) -> (18, []) d(16, alpha, N) -> (16, [P]) d(16, alpha, O) -> (16, []) d(16, beta, N) -> (16, [O; O; P]) d(16, beta, O) -> (16, [O; O]) d(16, c-phi, L) -> (16, []) d(16, gamma, P) -> (16, []) d(16, o-phi, B) -> (16, [N; L]) d(17, , !inital!) -> (16, [B; !inital!]) Q0: 2 Z0: !inital!
Final set status: [18] done!
Converting PDA into CFG...done! Clearing Grammar...Useful prods: AOD-> ZF^B AOJ-> BBB^B AYL-> BAF^V AYR-> BCZ^V AYU-> BEJ^V AYW-> BFB^V AZO-> alpha^Y AZO-> beta^W^W^Y B-> EPSILON BAF-> o-phi^AZO^X BAI-> alpha^E BAI-> beta^K^C^E BBB-> o-phi^BBE^H BBE-> alpha^I BBE-> beta^O^G^I BCZ-> o-phi^AZO^X BDO-> alpha^U BDO-> beta^T^T^U BEJ-> o-phi^AZO^X BFB-> o-phi^AZO^X C-> alpha C-> beta^K^C D-> c-phi E-> gamma F-> EPSILON G-> alpha G-> beta^O^G H-> c-phi I-> gamma J-> EPSILON K-> alpha K-> beta^K^C L-> c-phi M-> gamma N-> EPSILON O-> alpha O-> beta^O^G P-> c-phi Q-> gamma R-> EPSILON T-> alpha T-> beta^T^T T-> c-phi U-> gamma V-> EPSILON W-> alpha W-> beta^W^W X-> c-phi Y-> gamma Z-> alpha^E Z-> beta^K^C^E ZF-> o-phi^ZK^H ZK-> alpha^I ZK-> beta^O^G^I Nullable symbols: [B; F; J; N; R; V]Removed Epsilon productions: AOD-> ZF AOD-> ZF^B AOJ-> BBB AOJ-> BBB^B AYL-> BAF AYL-> BAF^V AYR-> BCZ AYR-> BCZ^V AYU-> BEJ AYU-> BEJ^V AYW-> BFB AYW-> BFB^V AZO-> alpha^Y
AZO-> beta^W^W^Y BAF-> o-phi^AZO^X BAI-> alpha^E BAI-> beta^K^C^E BBB-> o-phi^BBE^H BBE-> alpha^I BBE-> beta^O^G^I BCZ-> o-phi^AZO^X BDO-> alpha^U BDO-> beta^T^T^U BEJ-> o-phi^AZO^X BFB-> o-phi^AZO^X C-> alpha C-> beta^K^C D-> c-phi E-> gamma G-> alpha G-> beta^O^G H-> c-phi I-> gamma K-> alpha K-> beta^K^C L-> c-phi M-> gamma O-> alpha O-> beta^O^G P-> c-phi Q-> gamma T-> alpha T-> beta^T^T T-> c-phi U-> gamma W-> alpha W-> beta^W^W X-> c-phi Y-> gamma Z-> alpha^E Z-> beta^K^C^E ZF-> o-phi^ZK^H ZK-> alpha^I ZK-> beta^O^G^I
Non unit productions: AOD-> ZF^B AOJ-> BBB^B AYL-> BAF^V AYR-> BCZ^V AYU-> BEJ^V AYW-> BFB^V AZO-> alpha^Y AZO-> beta^W^W^Y BAF-> o-phi^AZO^X BAI-> alpha^E BAI-> beta^K^C^E BBB-> o-phi^BBE^H BBE-> alpha^I BBE-> beta^O^G^I BCZ-> o-phi^AZO^X BDO-> alpha^U BDO-> beta^T^T^U BEJ-> o-phi^AZO^X BFB-> o-phi^AZO^X C-> alpha C-> beta^K^C D-> c-phi E-> gamma G-> alpha G-> beta^O^G H-> c-phi I-> gamma K-> alpha K-> beta^K^C L-> c-phi M-> gamma O-> alpha O-> beta^O^G P-> c-phi Q-> gamma T-> alpha T-> beta^T^T T-> c-phi U-> gamma W-> alpha W-> beta^W^W X-> c-phi Y-> gamma Z-> alpha^E Z-> beta^K^C^E ZF-> o-phi^ZK^H ZK-> alpha^I ZK-> beta^O^G^I Removed unit prod: NT:
[AOD; AOJ; AYL; AYR; AYU; AYW; AZO; BAF; BAI; BBB; BBE; BCZ; BDO; BEJ; BFB; C; D; E; G; H; I; K; L; M; O; P; Q; T; U; W; X; Y; Z; ZF; ZK]
T:
[; alpha; beta; c-phi; gamma; o-phi] PROD: AOD-> ZF^B AOD-> o-phi^ZK^H AOJ-> BBB^B AOJ-> o-phi^BBE^H AYL-> BAF^V AYL-> o-phi^AZO^X AYR-> BCZ^V AYR-> o-phi^AZO^X AYU-> BEJ^V AYU-> o-phi^AZO^X AYW-> BFB^V AYW-> o-phi^AZO^X AZO-> alpha^Y AZO-> beta^W^W^Y BAF-> o-phi^AZO^X BAI-> alpha^E BAI-> beta^K^C^E BBB-> o-phi^BBE^H BBE-> alpha^I BBE-> beta^O^G^I BCZ-> o-phi^AZO^X BDO-> alpha^U BDO-> beta^T^T^U BEJ-> o-phi^AZO^X BFB-> o-phi^AZO^X C-> alpha C-> beta^K^C D-> c-phi
E-> gamma G-> alpha G-> beta^O^G H-> c-phi I-> gamma K-> alpha K-> beta^K^C L-> c-phi M-> gamma O-> alpha O-> beta^O^G P-> c-phi Q-> gamma T-> alpha T-> beta^T^T T-> c-phi U-> gamma W-> alpha W-> beta^W^W X-> c-phi Y-> gamma Z-> alpha^E Z-> beta^K^C^E ZF-> o-phi^ZK^H ZK-> alpha^I ZK-> beta^O^G^I S :S Pruned Unused: NT: [S] T:
[; alpha; beta; c-phi; gamma; o-phi] PROD:
S :S
Merged Equal productions: NT:
[S] T:
[; alpha; beta; c-phi; gamma; o-phi] PROD:
S :S done!
Checking for useful symbols... Initial New V:
[]
Initial Old V: []
Final set: []
The Grammar is Empty: true
All Policies Respected in Location -1 All Policies Respected in All Location By Plan Work[1].Empty
<===========>
