Ngôn ngữ do Ngữ pháp tạo ra
Tập hợp tất cả các chuỗi có thể bắt nguồn từ một ngữ pháp được cho là ngôn ngữ được tạo ra từ ngữ pháp đó. Một ngôn ngữ được tạo ra bởi một ngữ phápG là một tập hợp con được xác định chính thức bởi
L (G) = {W | W ∈ ∑ *, S ⇒ G W}
Nếu L(G1) = L(G2), ngữ pháp G1 tương đương với Ngữ pháp G2.
Thí dụ
Nếu có một ngữ pháp
G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}
Đây S sản xuất ABvà chúng tôi có thể thay thế A bởi avà B bởi b. Ở đây, chuỗi duy nhất được chấp nhận làab, I E,
L (G) = {ab}
Thí dụ
Giả sử chúng ta có ngữ pháp sau:
G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA | a, B → bB | b}
Ngôn ngữ do ngữ pháp này tạo ra -
L (G) = {ab, a 2 b, ab 2 , a 2 b 2 , ………}
= {a m b n | m ≥ 1 và n ≥ 1}
Xây dựng ngữ pháp Tạo ra một ngôn ngữ
Chúng tôi sẽ xem xét một số ngôn ngữ và chuyển nó thành ngữ pháp G tạo ra các ngôn ngữ đó.
Thí dụ
Problem- Giả sử, L (G) = {a m b n | m ≥ 0 và n> 0}. Chúng ta phải tìm ra ngữ phápG sản xuất L(G).
Solution
Vì L (G) = {a m b n | m ≥ 0 và n> 0}
tập hợp các chuỗi được chấp nhận có thể được viết lại thành -
L (G) = {b, ab, bb, aab, abb, …….}
Ở đây, biểu tượng bắt đầu phải có ít nhất một chữ 'b' đứng trước bất kỳ số 'a' nào kể cả null.
Để chấp nhận tập hợp chuỗi {b, ab, bb, aab, abb, …….}, Chúng tôi đã thực hiện các sản phẩm -
S → aS, S → B, B → b và B → bB
S → B → b (Được chấp nhận)
S → B → bB → bb (Được chấp nhận)
S → aS → aB → ab (Được chấp nhận)
S → aS → aaS → aaB → aab (Được chấp nhận)
S → aS → aB → abB → abb (Được chấp nhận)
Do đó, chúng ta có thể chứng minh mọi chuỗi đơn trong L (G) đều được chấp nhận bởi ngôn ngữ do tập sản xuất tạo ra.
Do đó ngữ pháp -
G: ({S, A, B}, {a, b}, S, {S → aS | B, B → b | bB})
Thí dụ
Problem- Giả sử, L (G) = {a m b n | m> 0 và n ≥ 0}. Chúng ta phải tìm ra ngữ pháp G tạo ra L (G).
Solution -
Vì L (G) = {a m b n | m> 0 và n ≥ 0}, tập hợp các chuỗi được chấp nhận có thể được viết lại thành -
L (G) = {a, aa, ab, aaa, aab, abb, …….}
Ở đây, ký hiệu bắt đầu phải nhận ít nhất một chữ 'a' theo sau là bất kỳ số chữ 'b' nào kể cả null.
Để chấp nhận tập hợp chuỗi {a, aa, ab, aaa, aab, abb, …….}, Chúng tôi đã thực hiện các sản phẩm -
S → aA, A → aA, A → B, B → bB, B → λ
S → aA → aB → aλ → a (Được chấp nhận)
S → aA → aaA → aaB → aaλ → aa (Được chấp nhận)
S → aA → aB → abB → abλ → ab (Chấp nhận)
S → aA → aaA → aaaA → aaaB → aaaλ → aaa (Được chấp nhận)
S → aA → aaA → aaB → aabB → aabλ → aab (Được chấp nhận)
S → aA → aB → abB → abbB → abbλ → abb (Chấp nhận)
Do đó, chúng ta có thể chứng minh mọi chuỗi đơn trong L (G) đều được chấp nhận bởi ngôn ngữ do tập sản xuất tạo ra.
Do đó ngữ pháp -
G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB})