문법에 의해 생성 된 언어

문법에서 파생 될 수있는 모든 문자열 집합은 해당 문법에서 생성 된 언어라고합니다. 문법에 의해 생성 된 언어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})