오토마타 프로그래밍 프로젝트
Chomsky 정규형(Chomsky normal form)으로 표현된 문맥-무관 문법(context-free grammar) G가 주어져 있다. G의 변수들은 영문 대문자로 이루어져 있고, 터미널 심벌들은 영어 소문자로 이루어져 있으며, S가 start symbol이라고 가정한다.
영문 소문자로 구성된 스트링 w가 주어질 때, w가 G가 생성하는 언어 L(G)의 원소인지 아닌지를 판별하는 프로그램을 작성하시오.
CYK 알고리즘
CYK 알고리즘(Cocke-Younger-Kasami 알고리즘, CYK Algorithm)은 특정한 문자열에 대해, 그 문자열이 특정한 문맥 자유 문법에 속하는지를 판단하고, 또한 어떠한 방식으로 생성되는지를 판단하는 파싱 알고리즘이다. 이 알고리즘은 동적 계획법을 사용하며, 상향식 파싱 구조를 가지고 있다.
기본적으로 CYK 알고리즘에서는 촘스키 정규 형식으로 표현된 문맥 자유 문법을 사용하지만, 모든 문맥 자유 문법은 촘스키 정규 형식으로 변환이 가능하기 때문에 CYK 알고리즘을 사용할 수 있다.
문자열의 길이가 n일 때, CYK 알고리즘은 Θ(n3)의 시간 복잡도를 가진다. 이것은 현재 모든 문맥 자유 문법을 파싱할 수 있는 가장 효율적인 알고리즘이다. (CYK 알고리즘보다 효율적으로 동작하는 몇몇 알고리즘이 있지만, 그 알고리즘은 특정한 문법의 경우에만 사용이 가능하다.)
예시 (입출력)
baaba // string w 5 // number of production rule // production rule of G S->AB S->BC A->BA A->a B->CC B->b C->AB C->a
{S,A,C}가 w를 Accept하므로 w는 L(G)의 원소이다.
C 프로그래밍
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX 101
typedef struct {
char left;
char right[3];
}prType;
typedef struct {
char str[MAX];
int size;
}string;
char* w; // string w
char* tmp; // temp string
prType* pr; // production rule
string dptable[MAX][MAX]; // fill dptable[i][j] using dptable[i][k] + dptable[k+1][j]
// check if string have character
bool have_char(char* str, char c, int len) {
for (int idx = 0; idx < len; idx++) {
if (str[idx] == c)
return 1;
}
return 0;
}
// check production rule and fill dptable[i][j]
void check_fill_dp(int i, int j, int m, char* str) {
for (int itr = 0; itr < m; itr++) {
// check if pr[itr].right and str are same string --- ex) pr[itr].right "AB" == str "AB"
if (!strcmp(pr[itr].right, str)) {
// check if dp[i][j] have pr[itr].left --- ex) dptable[i][j].str = 'S', pr[itr].left = 'B'
int len = strlen(dptable[i][j].str);
if (!have_char(dptable[i][j].str, pr[itr].left, len)) {
// add pr[itr].left to dp[i][j] --- ex) dptable[i][j].str = "SB"
int size = dptable[i][j].size++;
dptable[i][j].str[size] = pr[itr].left;
}
}
}
}
// fill dptable
void fill_dp(int wlen, int m) {
// init element size
for (int i = 0; i < wlen; i++) {
for (int j = 0; j < wlen; j++) {
dptable[i][j].size = 0;
}
}
// fill dptable[i][i]
// ex) dp[0][0], [1][1], [2][2], [3][3], [4][4]
for (int i = 0; i < wlen; i++) {
char str[2];
str[0] = w[i]; str[1] = 0;
check_fill_dp(i, i, m, str);
}
// fill dptable[i][j]
// ex) (dp[0][1], [1][2], [2,3], [3,4]) -> (dp[0][2], [1][3], [2,4]) -> (dp[0][3], [1][4]) -> (dp[0][4])
for (int idx1 = 1; idx1 < wlen; idx1++) {
for (int idx2 = 0; idx2 < wlen - idx1; idx2++) {
/*
cyk algorithm
fill dptable[i][j] using dptable[i][k] + dptable[k+1][j]
for k in range(i,j)
*/
int i = idx2;
int j = idx1 + idx2;
for (int k = i; k < j; k++) {
for (int e1 = 0; e1 < strlen(dptable[i][k].str); e1++) {
for (int e2 = 0; e2 < strlen(dptable[k+1][j].str); e2++) {
char str[3];
str[0] = dptable[i][k].str[e1];
str[1] = dptable[k+1][j].str[e2];
str[2] = 0;
check_fill_dp(i, j, m, str);
}
}
}
}
}
}
// show dptable matrix
void show_dp(int size) {
printf("\ndp[i,j]\t");
for (int i = 0; i < size; i++)
printf("%d(%c)\t", i + 1,w[i]);
printf("\n");
for (int i = 0; i < size; i++)
{
printf("%d\t", i + 1);
for (int j = 0; j < size; j++)
printf("%s\t", dptable[i][j].str);
printf("\n");
}
printf("\n");
}
int main()
{
// save string w
w = (char*)malloc(sizeof(char)*MAX);
scanf("%s",w);
int wlen = strlen(w); // length of w
// save production rule
int m; // num of production rule
scanf("%d", &m);
pr = (prType*)malloc(sizeof(prType)*m);
tmp = (char*)malloc(sizeof(char)*MAX);
for (int i = 0; i < m; i++) {
scanf("%s",tmp);
int idx = 0;
pr[i].left = tmp[0]; // ex) "S->AB" -> pr[0].left = 'S'
for (int j = 3; j < strlen(tmp); j++) { // ex) "S->AB" -> pr[0].right = "AB"
pr[i].right[idx++] = tmp[j];
}
pr[i].right[idx] = 0;
}
// fill dptable
fill_dp(wlen,m);
// check if w is an element of L(G)
if (dptable[0][wlen - 1].size > 0)
printf("yes");
else
printf("no");
return 0;
}
