CFG는 문맥 자유 문법을 의미합니다. 주어진 형식 언어에서 가능한 모든 문자열 패턴을 생성하는 데 사용되는 형식 문법입니다. 문맥 자유 문법 G는 다음과 같이 4개의 튜플로 정의될 수 있습니다.
G = (V, T, P, S)
어디,
G 생성 규칙의 집합으로 구성된 문법입니다. 언어의 문자열을 생성하는 데 사용됩니다.
티 터미널 기호의 마지막 세트입니다. 소문자로 표시됩니다.
안에 비 터미널 기호의 최종 세트입니다. 대문자로 표시됩니다.
피 문자열의 비터미널 기호(프로덕션의 왼쪽)를 다른 터미널 또는 비터미널 기호(프로덕션의 오른쪽)로 바꾸는 데 사용되는 생성 규칙 집합입니다.
4분기
에스 문자열을 파생하는 데 사용되는 시작 기호입니다. 모든 비터미널이 터미널 기호로 대체될 때까지 생성의 오른쪽으로 비터미널을 반복적으로 대체하여 문자열을 파생할 수 있습니다.
예시 1:
집합 ∑= {a}에 대해 임의 개수의 a를 갖는 언어에 대한 CFG를 구성합니다.
해결책:
우리가 알고 있듯이 위 언어의 정규식은 다음과 같습니다.
r.e. = a*
정규식의 생성 규칙은 다음과 같습니다.
S → aS rule 1 S → ε rule 2
이제 문자열 'aaaaaa'를 파생하려면 시작 기호로 시작할 수 있습니다.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
거기. = a*는 문자열 집합 {ε, a, aa, aaa,.....}를 생성할 수 있습니다. S는 시작 기호이고 규칙 2는 S → ε을 제공하므로 널 문자열을 가질 수 있습니다.
예 2:
정규식 (0+1)에 대한 CFG 구성*
해결책:
자바의 객체 배열
CFG는 다음과 같이 주어질 수 있습니다.
Production rule (P): S → 0S | 1S S → ε
규칙은 시작 기호와 함께 0과 1의 조합으로 되어 있습니다. (0+1)*은 {ε, 0, 1, 01, 10, 00, 11, ....}을 나타냅니다. 이 집합에서 ε은 문자열이므로 규칙에서 S → ε 규칙을 설정할 수 있습니다.
예시 3:
언어 L = w € (a, b)*에 대한 CFG를 구성합니다.
해결책:
특정 언어에 대해 생성할 수 있는 문자열은 {aacaa, bcb, abcba, bacab, abbcbba, ....}입니다.
문법은 다음과 같습니다.
S → aSa rule 1 S → bSb rule 2 S → c rule 3
이제 문자열 'abbcbba'를 파생시키려면 시작 기호로 시작할 수 있습니다.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
따라서 이러한 종류의 문자열은 모두 주어진 생성 규칙에서 파생될 수 있습니다.
예시 4:
언어 L = a에 대한 CFG를 구성합니다.N비2n여기서 n>=1입니다.
해결책:
특정 언어에 대해 생성할 수 있는 문자열은 {abb, aabbbb, aaabbbbbbb....}입니다.
자바 정렬의 arraylist
문법은 다음과 같습니다.
S → aSbb | abb
이제 문자열 'aabbbb'를 파생시키려면 시작 기호로 시작할 수 있습니다.
S → aSbb S → aabbbb