Dada una máquina en el lenguaje formal de N estados y M pares de combinaciones de salida en forma de array 2D arr[][] . Cada fila (digamos r ) de arr[][] indica los Nodes de ‘A’ a ‘Z’ y cada par de una columna (digamos (a, b) ) indica el cambio de estado del Node r al Node a través del estado segundo _ La tarea es encontrar los bordes compatibles y no compatibles del lenguaje formal.
Nota: se dice que Edge (A, B) es compatible ya que todos los siguientes estados y salidas son iguales o no están especificados en A, B correspondientes a cada columna.
Ejemplo:
Entrada: N = 6, M = 4,
arr[][] = { { ‘-‘, ‘-‘, ‘C’, ‘1’, ‘E’, ‘1’, ‘B’, ‘1’ } ,
{ ‘E’, ‘0’, ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘ },
{ ‘F’, ‘0’, ‘F’, ‘1 ‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘ },
{ ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘B’, ‘1’, ‘-‘, ‘- ‘ },
{ ‘-‘, ‘-‘, ‘F’, ‘0’, ‘A’, ‘0’, ‘D’, ‘1’ },
{ ‘C’, ‘0’, ‘-‘, ‘-‘, ‘B’, ‘0’, ‘C’, ‘1’ } }
Salida:
Bordes no compatibles
(A, E) (A, F) (B, F) (C, E) (D, E ) (D, F)
Bordes compatibles
(A, B)(A, C)(A, D)(B, C)(B, D)(B, E)(C, D)(C, F)(E) , F)
Entrada: N = 4, M = 4,
arr[][] = { { ‘-‘, ‘-‘, ‘C’, ‘1’, ‘E’, ‘1’, ‘B’, ‘ 1’ },
{ ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘B’, ‘1’, ‘-‘, ‘-‘ },
{ ‘-‘, ‘-‘, ‘F’ , ‘0’, ‘A’, ‘0’, ‘D’, ‘1’ },
{ ‘C’, ‘0’, ‘-‘, ‘-‘, ‘B’, ‘0’, ‘C’, ‘1’ } }
Salida:
bordes no compatibles
(A, C) (A, D) ( B, C) (B, D)
Bordes compatibles
(A, B)(C, D)
Acercarse:
- Para todas las combinaciones posibles (digamos (a,b) ) de los Nodes, verifique si hay algún camino posible presente en el lenguaje formal a través de cualquier número de estados como:
- Si el estado a través del Node a está vacío , busque el siguiente par de Nodes.
- Si el estado atravesado actual (por ejemplo, el Node b ) a través del Node a no está vacío y si el estado de salida a través del Node a al Node b no es el mismo, entonces verifique recursivamente la ruta del Node a al Node b .
- Si el estado de salida es el mismo, entonces tiene un borde directo entre el Node a y el Node b .
- Si la ruta se encuentra entre cualquier par de Nodes, entonces el par de Nodes es parte de un Node compatible.
- Almacene el par anterior de Nodes compatibles en una array Mat[][] .
- Recorra el Mat[][] para todos los pares posibles, y si ese par está presente en Mat[][], entonces imprímalo como Nodes compatibles De lo contrario, es un Node No compatible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int M = 8;
// Function to find the compatible and
// non-compatible for a given formal language
void findEdges(char arr[][M], int n, int m)
{
// To store the compatible edges
char mat[1000][1000] = { 'x' };
// Loop over every pair of nodes in the
// given formal language
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Traverse through the output
// column and compare it between
// each set of pairs of nodes
for (int k = 0; k < 2 * m; k += 2) {
// If the output is not
// specified then leave the
// edge unprocessed
if (arr[i][k + 1] == '-'
|| arr[j][k + 1] == '-') {
continue;
}
// If the output of states
// doesn't match then not
// compatible.
if (arr[i][k + 1] != arr[j][k + 1]) {
// Mark the not compatible
// edges in the matrix with
// character 'v'
mat[i][j] = 'v';
mat[j][i] = 'v';
break;
}
}
}
}
int nn = n;
// Loop over all node to find other non
// compatible edges
while (nn--) {
// Loop over every pair of nodes in
// the given formal language
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int k;
for (k = 0; k < m; k += 2) {
// If the output is
// not specified then
// leave edge unprocessed
if (arr[i][k + 1] == '-'
|| arr[j][k + 1] == '-') {
continue;
}
// If output is not equal
// then break as non-compatible
if (arr[i][k + 1] != arr[j][k + 1]) {
break;
}
}
if (k < m) {
continue;
}
for (k = 0; k < m; k += 2) {
// If next states are unspecified
// then continue
if (arr[i][k] == '-'
|| arr[j][k] == '-') {
continue;
}
// If the states are not equal
if (arr[i][k] != arr[j][k]) {
int x = arr[i][k] - 'A';
int y = arr[j][k] - 'A';
// If the dependent edge
// is not compatible then
// this edge is also not
// compatible
if (mat[x][y] == 'v') {
mat[i][j] = 'v';
mat[j][i] = 'v';
break;
}
}
}
}
}
}
// Output all Non-compatible Edges
printf("Not Compatible Edges \n");
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (mat[i][j] == 'v') {
printf("(%c, %c) ", i + 65, j + 65);
}
}
}
printf("\n");
// Output all Compatible Edges
printf("Compatible Edges \n");
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (mat[i][j] != 'v') {
printf("(%c, %c)", i + 65, j + 65);
}
}
}
}
// Driver Code
int main()
{
int n = 6, m = 4;
char arr[][8] = { { '-', '-', 'C', '1', 'E', '1', 'B', '1' },
{ 'E', '0', '-', '-', '-', '-', '-', '-' },
{ 'F', '0', 'F', '1', '-', '-', '-', '-' },
{ '-', '-', '-', '-', 'B', '1', '-', '-' },
{ '-', '-', 'F', '0', 'A', '0', 'D', '1' },
{ 'C', '0', '-', '-', 'B', '0', 'C', '1' } };
findEdges(arr, n, m);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
static int M = 8;
// Function to find the compatible and
// non-compatible for a given formal language
static void findEdges(char arr[][], int n, int m)
{
// To store the compatible edges
char [][]mat = new char[1000][1000];
// Loop over every pair of nodes in the
// given formal language
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Traverse through the output
// column and compare it between
// each set of pairs of nodes
for(int k = 0; k < 2 * m; k += 2)
{
// If the output is not
// specified then leave the
// edge unprocessed
if (arr[i][k + 1] == '-' ||
arr[j][k + 1] == '-')
{
continue;
}
// If the output of states
// doesn't match then not
// compatable.
if (arr[i][k + 1] != arr[j][k + 1])
{
// Mark the not compatable
// edges in the matrix with
// character 'v'
mat[i][j] = 'v';
mat[j][i] = 'v';
break;
}
}
}
}
int nn = n;
// Loop over all node to find other non
// compatable edges
while (nn-- > 0)
{
// Loop over every pair of nodes in
// the given formal language
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
int k;
for(k = 0; k < m; k += 2)
{
// If the output is
// not specified then
// leave edge unprocessed
if (arr[i][k + 1] == '-' ||
arr[j][k + 1] == '-')
{
continue;
}
// If output is not equal
// then break as non-compatable
if (arr[i][k + 1] !=
arr[j][k + 1])
{
break;
}
}
if (k < m)
{
continue;
}
for(k = 0; k < m; k += 2)
{
// If next states are unspecified
// then continue
if (arr[i][k] == '-' ||
arr[j][k] == '-')
{
continue;
}
// If the states are not equal
if (arr[i][k] != arr[j][k])
{
int x = arr[i][k] - 'A';
int y = arr[j][k] - 'A';
// If the dependent edge
// is not compatable then
// this edge is also not
// compatable
if (mat[x][y] == 'v')
{
mat[i][j] = 'v';
mat[j][i] = 'v';
break;
}
}
}
}
}
}
// Output all Non-compatable Edges
System.out.printf("Not Compatable Edges \n");
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
if (mat[i][j] == 'v')
{
System.out.printf("(%c, %c) ",
i + 65, j + 65);
}
}
}
System.out.printf("\n");
// Output all Compatable Edges
System.out.printf("Compatable Edges \n");
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
if (mat[i][j] != 'v')
{
System.out.printf("(%c, %c)",
i + 65, j + 65);
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int n = 6, m = 4;
char arr[][] = { { '-', '-', 'C', '1',
'E', '1', 'B', '1' },
{ 'E', '0', '-', '-',
'-', '-', '-', '-' },
{ 'F', '0', 'F', '1',
'-', '-', '-', '-' },
{ '-', '-', '-', '-',
'B', '1', '-', '-' },
{ '-', '-', 'F', '0',
'A', '0', 'D', '1' },
{ 'C', '0', '-', '-',
'B', '0', 'C', '1' } };
findEdges(arr, n, m);
}
}
// This code is contributed by Amit Katiyar
C#
// C# implementation of
// the above approach
using System;
class GFG{
static int M = 8;
// Function to find the
//compatible and non-compatible
// for a given formal language
static void findEdges(char [,]arr,
int n, int m)
{
// To store the compatible edges
char [,]mat = new char[1000, 1000];
// Loop over every pair of
// nodes in the given
// formal language
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Traverse through the output
// column and compare it between
// each set of pairs of nodes
for(int k = 0; k < 2 * m; k += 2)
{
// If the output is not
// specified then leave the
// edge unprocessed
if (arr[i, k + 1] == '-' ||
arr[j, k + 1] == '-')
{
continue;
}
// If the output of states
// doesn't match then not
// compatable.
if (arr[i, k + 1] != arr[j, k + 1])
{
// Mark the not compatable
// edges in the matrix with
// character 'v'
mat[i, j] = 'v';
mat[j, i] = 'v';
break;
}
}
}
}
int nn = n;
// Loop over all node to find other non
// compatable edges
while (nn-- > 0)
{
// Loop over every pair of nodes in
// the given formal language
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
int k;
for(k = 0; k < m; k += 2)
{
// If the output is
// not specified then
// leave edge unprocessed
if (arr[i, k + 1] == '-' ||
arr[j, k + 1] == '-')
{
continue;
}
// If output is not equal
// then break as non-compatable
if (arr[i, k + 1] !=
arr[j, k + 1])
{
break;
}
}
if (k < m)
{
continue;
}
for(k = 0; k < m; k += 2)
{
// If next states are unspecified
// then continue
if (arr[i, k] == '-' ||
arr[j, k] == '-')
{
continue;
}
// If the states are not equal
if (arr[i, k] != arr[j, k])
{
int x = arr[i, k] - 'A';
int y = arr[j, k] - 'A';
// If the dependent edge
// is not compatable then
// this edge is also not
// compatable
if (mat[x, y] == 'v')
{
mat[i, j] = 'v';
mat[j, i] = 'v';
break;
}
}
}
}
}
}
// Output all Non-compatable Edges
Console.Write("Not Compatable Edges \n");
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
if (mat[i, j] == 'v')
{
Console.Write("({0}, {1}) ",
(char)(i + 65),
(char)(j + 65));
}
}
}
Console.Write("\n");
// Output all Compatable Edges
Console.Write("Compatable Edges \n");
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
if (mat[i, j] != 'v')
{
Console.Write("({0}, {1})",
(char)(i + 65),
(char)(j + 65));
}
}
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 6, m = 4;
char [,]arr = {{'-', '-', 'C', '1',
'E', '1', 'B', '1'},
{'E', '0', '-', '-',
'-', '-', '-', '-'},
{'F', '0', 'F', '1',
'-', '-', '-', '-'},
{'-', '-', '-', '-',
'B', '1', '-', '-'},
{'-', '-', 'F', '0',
'A', '0', 'D', '1'},
{'C', '0', '-', '-',
'B', '0', 'C', '1'}};
findEdges(arr, n, m);
}
}
// This code is contributed by 29AjayKumar
metro
Complejidad de tiempo: O(M*N 3 ), donde N es el número de estados y M es la salida para cada estado.
Publicación traducida automáticamente
Artículo escrito por bhagatsunny96 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA