문법에 의해 생성 된 언어
문법에서 파생 될 수있는 모든 문자열 집합은 해당 문법에서 생성 된 언어라고합니다. 문법에 의해 생성 된 언어G 공식적으로 정의한 하위 집합입니다.
L (G) = {W | W ∈ ∑ *, S ⇒ G W}
만약 L(G1) = L(G2), 문법 G1 문법과 동일 G2.
예
문법이 있다면
G : N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}
여기 S 생산하다 AB, 우리는 A 으로 a, 및 B 으로 b. 여기서 허용되는 유일한 문자열은ab즉,
L (G) = {ab}
예
다음과 같은 문법이 있다고 가정합니다.
G : N = {S, A, B} T = {a, b} P = {S → AB, A → aA | a, B → bB | b}
이 문법에 의해 생성 된 언어-
L (G) = {ab, a 2 b, ab 2 , a 2 b 2 , ………}
= {a m b n | m ≥ 1 및 n ≥ 1}
언어를 생성하는 문법의 구성
우리는 일부 언어를 고려하여 해당 언어를 생성하는 문법 G로 변환 할 것입니다.
예
Problem− L (G) = {a m b n | m ≥ 0 및 n> 0}. 문법을 찾아야합니다G 생산하는 L(G).
Solution
L (G) = {a m b n | m ≥ 0 및 n> 0}
허용되는 문자열 세트는 다음과 같이 다시 작성할 수 있습니다.
L (G) = {b, ab, bb, aab, abb, …….}
여기서 시작 기호는 널을 포함하여 임의의 수의 'a'가 앞에 오는 하나 이상의 'b'를 가져야합니다.
문자열 세트 {b, ab, bb, aab, abb, …….}를 받아들이 기 위해 우리는 프로덕션을 취했습니다.
S → aS, S → B, B → b 및 B → bB
S → B → b (허용됨)
S → B → bB → bb (허용됨)
S → aS → aB → ab (허용됨)
S → aS → aaS → aaB → aab (허용됨)
S → aS → aB → abB → abb (허용됨)
따라서 L (G)의 모든 단일 문자열이 프로덕션 세트에서 생성 된 언어에 의해 허용된다는 것을 증명할 수 있습니다.
따라서 문법-
G : ({S, A, B}, {a, b}, S, {S → aS | B, B → b | bB})
예
Problem− L (G) = {a m b n | m> 0 및 n ≥ 0}. L (G)를 생성하는 문법 G를 찾아야합니다.
Solution −
L (G) = {a m b n | m> 0 및 n ≥ 0}, 허용되는 문자열 세트는 다음과 같이 다시 쓸 수 있습니다.
L (G) = {a, aa, ab, aaa, aab, abb, …….}
여기서 시작 기호는 적어도 하나의 'a'다음에 널을 포함하여 'b'를 가져와야합니다.
문자열 세트 {a, aa, ab, aaa, aab, abb, …….}를 받아들이 기 위해 우리는 프로덕션을 취했습니다
S → aA, A → aA, A → B, B → bB, B → λ
S → aA → aB → aλ → a (허용됨)
S → aA → aaA → aaB → aaλ → aa (허용됨)
S → aA → aB → abB → abλ → ab (허용됨)
S → aA → aaA → aaaA → aaaB → aaaλ → aaa (허용됨)
S → aA → aaA → aaB → aabB → aabλ → aab (허용됨)
S → aA → aB → abB → abbB → abbλ → abb (허용됨)
따라서 L (G)의 모든 단일 문자열이 프로덕션 세트에서 생성 된 언어에 의해 허용된다는 것을 증명할 수 있습니다.
따라서 문법-
G : ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB})