2) Văn phạm không nhập nhằng tương đương. S → S + T | S - T | S * T | S / T | T ;
T → ( S ) | a .
3.30. 1) S → A | aSb | a; A → AB; B → b
a) Loại bỏ biến không sinh ra xâu các ký tự kết thúc
Áp dụng giải thuật loại bỏ biến không sinh ra xâu ký tự kết thúc, ta có:
1. G‟= (N‟, T‟, P‟, S‟):
T‟ = a, b S‟ = S; 2. N‟:
N‟ | Giải thích | |
KT | {S, B} | S → a; B → b |
1 | {S, B} | S → aSb | a; B → b |
Có thể bạn quan tâm!
-
Ngôn ngữ hình thức - 26 -
Ngôn ngữ hình thức - 27 -
Ngôn ngữ hình thức - 28 -
Ngôn ngữ hình thức - 30 -
Ngôn ngữ hình thức - 31
Xem toàn bộ 254 trang tài liệu này.
3. P‟= {S → aSb | a; B → b}.
b) Loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu
Áp dụng giải thuật loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu, ta có:
1. G1= (N1, T1, P1, S1):
S1 = S; 2. N1, T1:
N1 | T1 | Giải thích | |
KT | {S} | | |
1 | {S} | {a, b} | S → AB a |
2 | {S} | {a, b} | S → AB a |
3. P1 = {S → AB a }.
2) S → AB | CA; A → a; B → BC | AB; C → aB | b
a) Loại bỏ biến không sinh ra xâu các ký tự kết thúc
Áp dụng giải thuật loại bỏ biến không sinh ra xâu, ta có:
1. G‟= (N‟, T‟, P‟, S‟):
T‟ = a, b S‟ = S;
2. N‟:
N‟ | Giải thích | |
KT | {A, C} | A → a; C → b |
1 | {S, A, C} | S → CA; A → a; C → b |
2 | {S, A, C} | S → CA; A → a; C → b |
3. P‟= {S → CA; A → a; C → b}.
b) Loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu
Áp dụng giải thuật loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu, ta có:
1. G1= (N1, T1, P1, S1):
S1 = S; 2. N1, T1:
N1 | T1 | Giải thích | |
KT | {S} | | |
1 | {S, A, C} | | S → CA |
2 | {S, A, C} | {a, b} | S → CA; A → a; C → b |
3 | {S, A, C} | {a, b} | S → CA; A → a; C → b |
3. P1 = {S → CA; A → a; C → b}.
3.31. - Áp dụng giải thuật loại bỏ luật sinh ε, ta có tập các biến rỗng:
R-Nullable | Giải thích | |
KT | {B} | B → ε |
1 | {A, B} | A → BB |
2 | {S, A, B} | S → AB; A → BB |
3 | {S, A, B} | S → AB; A → A → SA | BB |
Tập biến rỗng Nullable = {S, A, B}
- Tập luật sinh P‟:
S → AB | A | B | ε;
A → SA | S | BB | B | bB | b; B → b | aA | a.
Vì L(G) nên phải bổ sung thêm luật sinh S → ε vào P‟.
3.32. 1) Loại bỏ ký hiệu thừa
a) Loại bỏ biến không sinh ra xâu các ký tự kết thúc
Áp dụng giải thuật loại bỏ biến không sinh ra xâu ký tự kết thúc, ta có:
1. G‟= (N‟, T‟, P‟, S‟):
T‟ = a, b S‟ = S; 2. N‟:
N‟ | Giải thích | |
KT | {S, A, B, C} | S → ; A → b; B→ ; C → |
1 | {S, A, B, C} | S → AB| A| ; A → aBb| bS| b; B → AB| Ba| ; C → Aa| |
2 | {S, A, B, C} | S → AB| A| ; A → aBb| bS| b; B → AB| Ba| ; C → Aa| |
3. P‟ = {S → AB| A| ; A → aBb| bS| b; B → AB| Ba| ; C → Aa| }.
b) Loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu
Áp dụng giải thuật loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu, ta có: 1. G1 = (N1, T1, P1, S1):
S1 = S;
2. N1, T1:
N1 | T1 | Giải thích | |
KT | {S} | | |
1 | {S, A, B} | {a, b} | S → AB | A |
2 | {S, A, B} | {a, b} | S → AB | A; A → aBb | bS| b; B → AB | Ba |
3. P1 = {S → AB | A | ; A → aBb | bS| b; B → AB | Ba | }.
2) Loại bỏ luật sinh ε
- Áp dụng giải thuật loại bỏ luật sinh ε, ta có tập các biến rỗng:
R-Nullable | Giải thích | |
KT | {S, B, C} | S → ε; B → ε; C → ε |
1 | {S, B, C} |
Tập biến rỗng Nullable = {S, B, C}
- Tập luật sinh P‟:
S → AB | A | ε;
A → aBb | ab | bS | b;
B → AB | A | Ba |a; C → Aa | D.
Vì L(G) nên phải bổ sung thêm luật sinh S → ε vào P‟.
3.33. 1) Loại bỏ ký hiệu thừa ký hiệu thừa
Theo bài tập 3.32, văn phạm tương đương không chứa ký hiệu thừa có tập luật sinh: S → AB | A | ; A → aBb | bS| b; B → AB | Ba | .
2) Loại bỏ luật sinh ε
- Áp dụng giải thuật loại bỏ luật sinh ε, ta có tập các biến rỗng:
R-Nullable | Giải thích | |
KT | {S, B} | S → ε; B → ε |
1 | {S, B} |
Tập biến rỗng Nullable = {S, B}
- Tập luật sinh P‟:
S → AB | A | ε;
A → aBb | ab | bS | b; B → AB | A | Ba |a;
Vì L(G) nên phải bổ sung thêm luật sinh S → ε vào P‟.
3) Loại bỏ luật sinh đơn vị
Áp dụng giải thuật loại bỏ luật sinh đơn vị , ta có G‟= (N‟, T‟, P‟, S‟):
- N‟ = {S, A, B}; T‟ = {a, b} ; S‟ = S ; P‟: S → AB | ε;
A → aBb | ab | bS | b; B → AB | Ba |a;
- Δ S = {A}; Δ B = {A}; Δ A= ;
- Với biến S, phải thêm vào P‟ các luật sinh S → aBb | ab | bS | b;
- Với biến B, phải thêm vào P‟ các luật sinh B → aBb | ab | bS | b;
Vậy tập luật sinh P‟, theo giải thuật sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau:
S → AB | aBb | ab | bS | b | ε;
A → aBb | ab | bS | b;
B → AB | aBb | ab | bS | b | Ba |a.
3.34. Tương tự các bài tập 3.33, ...
3.35. 1) Loại bỏ ký hiệu thừa
a) Loại bỏ biến không sinh ra xâu các ký tự kết thúc
Áp dụng giải thuật loại bỏ biến không sinh ra xâu ký tự kết thúc, ta có: 1. G‟= (N‟, T‟, P‟, S‟):
T‟ = a, b, c S‟ = S; 2. N‟:
N‟ | Giải thích | |
KT | {A, C} | A → a | ε; C → b | c | ε |
1 | {S, A, B,C} | S → A | aCA; A → a| ε; B → C; C → b | c | ε |
2 | {S, A, B, C} | S → A | aCA; A → a| ε; B → C | AbcB; C → aB | b | c | ε |
3. P‟ = {S → A | aCA; A → a | ε; B → C | AbcB; C → aB | b | c | ε}.
b) Loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu
Áp dụng giải thuật loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu, ta có:
1. G1= (N1, T1, P1, S1):
S1 = S; 2. N1, T1:
N1 | T1 | Giải thích | |
KT | {S} | | |
1 | {S, A, C} | {a} | S → A | aCA |
2 | {S, A, B, C} | {a, b, c} | S → A | aCA; A → a| ε; C → aB | b | c| ε |
3 | {S, A, B, C} | {a, b, c} | S→ A|aCA; A→ a| ε; B → C|AbcB; C → aB|b| c| ε |
3. P1 = {S → A | aCA; A → a | ε; B → C | AbcB; C → aB | b | c | ε}.
2) Loại bỏ luật sinh ε
- Áp dụng giải thuật loại bỏ luật sinh ε, ta có tập các biến rỗng:
R-Nullable | Giải thích | |
KT | {A, C} | A → ε; C → ε |
1 | {S, A, B, C} | S → A; B → C |
2 | {S, A, B, C} | S → A; B → C |
Tập biến rỗng Nullable = {S, A, B, C}
- Tập luật sinh P”:
S → A | aCA | aA | aC | a | ε; A → a;
B → C | AbcB | bcB | Abc | bc; C → aB | a | b | c
Vì L(G) nên phải bổ sung thêm luật sinh S → ε vào P”.
3) Loại bỏ luật sinh đơn vị
Áp dụng giải thuậtloại bỏ luật sinh đơn vị, ta có G‟1 = (N‟1, T‟1, P‟1, S‟1):
- N‟1 = {S, A, B, C}; T‟1 = {a, b, c} ; S‟1 = S ;
P‟1: S → aCA | aA | aC | a | ε; A → a;
B → AbcB | bcB | Abc | bc; C → aB | a | b | c
- Δ S = {A}; Δ B = {C}; Δ A= ; Δ C=
- Với biến S, phải thêm vào P‟1 luật sinh S → a;
- Với biến B, phải thêm vào P‟1 các luật sinh B → aB | a | b | c;
Vậy tập luật sinh P‟1, theo giải thuật sẽ chứa các luật sinh không là luật sinh đơn vị trong P1, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau:
P‟1: S → aCA | aA | aC | a | ε; A → a;
B → aB | a | b | c | AbcB | bcB | Abc | bc; C → aB | a | b | c.
3.36. 1) Nêu các thành phần của văn phạm (tự làm).
2) Tìm văn phạm tương đương với văn phạm trên không chứa ký hiệu thừa, luật sinh ε và luật sinh đơn vị.
a) Loại bỏ ký hiệu thừa
- Loại bỏ biến không sinh ra xâu các ký tự kết thúc
Áp dụng giải thuật loại bỏ biến không sinh ra xâu ký tự kết thúc, ta có: 1. G‟ = (N‟, T‟, P‟, S‟):
T‟ = a, b, c S‟ = S; 2. N‟:
N‟ | Giải thích | |
KT | {A, B, C} | A → ε; B → a; C → b | ε |
1 | {S, A, B,C} | S → A| AcBC; A → B; B → bCA | C |a; C → ABc | b |
2 | {S, A, B, C} | S → A| AcBC; A → B; B → bCA | C |a; C → ABc | b |
3. P‟ = {S → A| AcBC; A → B | ε; B → bCA | C |a; C → ABc | b| ε}.
b) Loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu
Áp dụng giải thuật loại bỏ các ký tự không được sinh ra từ ký tự bắt đầu, ta có:
1. G1= (N1, T1, P1, S1):
S1 = S; 2. N1, T1:
N1 | T1 | Giải thích | |
KT | {S} | | |
1 | {S, A, B, C} | {c} | S → A| AcBC |
2 | {S, A, B, C} | {a, b, c} | S→ A|aCA; A→B; B→bCA|C|a; C→ABc|b |
3 | {S, A, B, C} | {a, b, c} | S→ A|aCA; A→B; B→bCA|C|a; C→ABc|b |
3. P1 = {S → A| AcBC; A → B | ε; B → bCA | C |a; C → ABc | b| ε}.
c) Loại bỏ luật sinh ε
- Áp dụng giải thuật loại bỏ luật sinh ε, ta có tập các biến rỗng:
R-Nullable | Giải thích | |
KT | {A, C} | A → ε; C → ε |
1 | {S, A, B, C} | S → A; B → C |
2 | {S, A, B, C} | S → A; B → C |
Tập biến rỗng Nullable = {S, A, B, C}
- Tập luật sinh P”:
S → A| AcBC| cBC | AcC | AcB| cC| Ac| cB| c | ε; A → B;
B → bCA | bA | bC | b|C |a; C → ABc | Bc | Ac | c | b
Vì L(G) nên phải bổ sung thêm luật sinh S → ε vào P”.
d) Loại bỏ luật sinh đơn vị
Áp dụng giải thuật loại bỏ luật sinh đơn vị, ta có G‟1 = (N‟1, T‟1, P‟1, S‟1):
- N‟1 = {S, A, B, C}; T‟1 = {a, b, c} ; S‟1 = S ;
P‟1: S → AcBC| cBC | AcC | AcB| cC| Ac| cB| c | ε; B → bCA | bA | bC | b | a;
C → ABc | Bc | Ac | c | b
- Δ S = {A, B, C}; Δ A = {B, C}; Δ B = {C}; Δ C=
- Với biến S, phải thêm vào P‟1 luật sinh S → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b;
- Với biến A, phải thêm vào P‟1 các luật sinh A → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b;
- Với biến B, phải thêm vào P‟1 các luật sinh B → ABc | Bc | Ac | c | b;
Vậy tập luật sinh P‟1, theo giải thuật sẽ chứa các luật sinh không là luật sinh đơn vị trong P1, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau:
P‟1: S → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b | AcBC| cBC | AcC
| AcB| cC| Ac| cB| c | ε;