Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import "fmt"
- //var nn1, nn2 int
- type Graph struct {
- state, newState, depth, i int
- inputAlphabet, mark, newInputAlphabet string
- parent *Graph
- }
- //Поиск набора parent
- func Find(x *Graph) *Graph {
- if x.parent == x {
- return x
- }
- x.parent = Find(x.parent)
- return x.parent
- }
- //Объединения
- func Union(x, y *Graph) {
- rootX := Find(x)
- rootY := Find(y)
- if rootX.depth < rootY.depth {
- rootY.parent = rootY
- } else {
- rootY.parent = rootX
- if rootX.depth == rootY.depth && rootX != rootY {
- rootX.depth++
- }
- }
- }
- func Split1(phi [][] Graph, n, X, q int) (int, []int) {
- var m, x, q1, q2 int
- var eq bool
- var Q = make([] Graph, n)
- m = n
- q, q1 = 0, 0
- for q < n {
- Q[q].i = q
- Q[q].parent = &Q[q]
- Q[q].depth = 0
- q++
- }
- for q1 < n {
- q2 = 0
- for q2 < n {
- if Find(&Q[q1]) != Find(&Q[q2]) {
- eq = true
- x = 0
- for x < X {
- if phi[q1][x].inputAlphabet != phi[q2][x].inputAlphabet {
- eq = false
- break
- }
- x++
- }
- if eq {
- Union(&Q[q1], &Q[q2])
- m = m - 1
- }
- }
- q2++
- }
- q1++
- }
- var pi = make([] int, n)
- q = 0
- for q < n {
- pi[Q[q].i] = Find(&Q[q]).i
- q++
- }
- return m, pi
- }
- func Split(delta [][] Graph, pi[] int, n, X, q int) (int, []int) {
- var m, x, q1, q2 int
- var eq bool
- var Q = make([] Graph, n)
- m = n
- q, q1 = 0, 0
- for q < n {
- Q[q].i = q
- Q[q].parent = &Q[q]
- Q[q].depth = 0
- q++
- }
- for q1 < n {
- q2 = 0
- for q2 < n {
- if pi[Q[q1].i] == pi[Q[q2].i] && Find(&Q[q1]) != Find(&Q[q2]) {
- eq = true
- x = 0
- for x < X {
- w1 := delta[Q[q1].i][x].state
- w2 := delta[Q[q2].i][x].state
- if pi[w1] != pi[w2] {
- eq = false
- break
- }
- x++
- }
- if eq {
- Union(&Q[q1], &Q[q2])
- m = m - 1
- }
- }
- q2++
- }
- q1++
- }
- q = 0
- for q < n {
- pi[Q[q].i] = Find(&Q[q]).i
- q++
- }
- return m, pi
- }
- func AufenkampHohn(A [][] Graph, n, X, qq int) ([]Graph){
- var m1, m, q, x int
- var pi []int
- var matrixes = make([][]Graph, n, n)
- m, pi = Split1(A, n, X, qq)
- for {
- m1, pi = Split(A, pi, n, X, qq)
- if m == m1 {
- break
- }
- m = m1
- }
- for i := 0; i < n; i++ {
- matrixes[i] = make([] Graph, X)
- }
- var Q = make([] bool, n)
- for q < n {
- q1 := pi[q]
- if !Q[q1] {
- Q[q1] = true
- x = 0
- for x < X {
- matrixes[q1][x].state = pi[A[q][x].state]
- matrixes[q1][x].inputAlphabet = A[q][x].inputAlphabet
- x++
- }
- }
- q++
- }
- return DFS(matrixes, n, X, pi[qq])
- //return matrixes
- }
- func DFS(arr1[][] Graph, n, m, q int) ([]Graph){
- var sizeStack, count, i, j int
- var newMatrix = make([] Graph, n)
- var stack = make([]int, n*n)
- count = 0
- stack[0] = q
- sizeStack = 1
- for sizeStack > 0 {
- sizeStack--
- var v = stack[sizeStack]
- if newMatrix[v].mark != "black" {
- newMatrix[v].mark = "black"
- newMatrix[v].i = count
- count++
- }
- i = m - 1
- for i > -1 {
- u := arr1[v][i].state
- if newMatrix[u].mark != "black" {
- stack[sizeStack] = u
- sizeStack++
- }
- i--
- }
- }
- i = 0
- for i < n {
- if newMatrix[i].mark == "black" {
- j = 0
- for j < m {
- arr1[newMatrix[i].i][j].newState = newMatrix[arr1[i][j].state].i
- arr1[newMatrix[i].i][j].newInputAlphabet = arr1[i][j].inputAlphabet
- j++
- }
- }
- i++
- }
- return newMatrix
- //fmt.Print("digraph {\n", " rankdir = LR\n", " dummy [label = \"\", shape = none]\n")
- //for i := 0; i < count; i++ {
- // fmt.Print(" ", i, " [shape = circle]\n")
- //}
- //fmt.Print(" dummy -> ", 0, "\n")
- //for i := 0; i < count; i++ {
- // for j := 0; j < m; j++ {
- // fmt.Print(" ", i, " -> ", arr1[i][j].newState, " [label = \"", (string)(97+j), "(", arr1[i][j].newInputAlphabet, ")\"]\n")
- // }
- //}
- //fmt.Print("}")
- }
- func main() {
- //первый автомат
- var n, m, q0 int
- fmt.Scan(&n, &m, &q0) //количество состояний автомата, размер входного автомата, номер начального состояния
- var matrix = make([][] Graph, n, n)
- //матрица переходов
- for i := 0; i < n; i++ {
- matrix[i] = make([] Graph, m)
- for j := 0; j < m; j++ {
- fmt.Scan(&matrix[i][j].state)
- }
- }
- //матрица выходов
- for i := 0; i < n; i++ {
- for j := 0; j < m; j++ {
- fmt.Scan(&matrix[i][j].inputAlphabet)
- }
- }
- nn1 := AufenkampHohn(matrix, n, m, q0)
- //второй автомат
- var n1, m1, q1 int
- fmt.Scan(&n1, &m1, &q1) //количество состояний автомата, размер входного автомата, номер начального состояния
- var matrix1 = make([][] Graph, n1, n1)
- //матрица переходов
- for i := 0; i < n1; i++ {
- matrix1[i] = make([] Graph, m1)
- for j := 0; j < m1; j++ {
- fmt.Scan(&matrix1[i][j].state)
- }
- }
- //матрица выходов
- for i := 0; i < n1; i++ {
- for j := 0; j < m1; j++ {
- fmt.Scan(&matrix1[i][j].inputAlphabet)
- }
- }
- nn2 := AufenkampHohn(matrix1, n1, m1, q1)
- //for i := 0; i < n1; i++ {
- // for j := 0; j < m1; j++ {
- // if matrix[i][j].state != matrix1[i][j].state || matrix[i][j].inputAlphabet != matrix1[i][j].inputAlphabet{
- // break
- // fmt.Print("NOT EQUAL\n")
- //
- // } else if matrix[i][j].state == matrix1[i][j].state && matrix[i][j].inputAlphabet == matrix1[i][j].inputAlphabet{
- // fmt.Print("EQUAL\n")
- // }
- // }
- //}
- flag := true
- //if m == m1 {
- // flag = true
- //} else {
- if n < n1 {
- for i := 0; i < n; i++ {
- //for j := 0; j < m1; j++ {
- if nn1[i] == nn2[i] {
- //break
- //fmt.Print("EQUAL\n")
- flag = true
- } else { //else if matrix[i][j].state == matrix1[i][j].state && matrix[i][j].inputAlphabet == matrix1[i][j].inputAlphabet{
- //fmt.Print("NOT EQUAL\n")
- flag = false
- //break
- }
- }
- } else {
- for i := 0; i < n1; i++ {
- //for j := 0; j < m1; j++ {
- if nn1[i] == nn2[i] {
- //break
- //fmt.Print("EQUAL\n")
- flag = true
- } else { //else if matrix[i][j].state == matrix1[i][j].state && matrix[i][j].inputAlphabet == matrix1[i][j].inputAlphabet{
- //fmt.Print("NOT EQUAL\n")
- flag = false
- //break
- }
- }
- }
- //}
- //}
- if flag == true {
- fmt.Print("EQUAL\n")
- } else {
- fmt.Print("NOT EQUAL\n")
- }
- //if AufenkampHohn(matrix1, n1, m1, q1) == AufenkampHohn(matrix, n, m, q0) {
- // fmt.Print("EQUAL\n")
- //} else {
- //fmt.Print("NOT EQUAL\n")
- //}
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement