JavaScript phải có khả năng tiếp tục

Chia sẻ: Hoang Nguyen | Ngày: | Loại File: DOC | Số trang:9

Thêm vào BST

Báo xấu

59
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Điểm : 1 Cho văn phạm G: S ® aSa | bSb | e Bằng cách dẫn xuất một số chuỗi thuộc ngôn ngữ, hãy cho biết ngôn ngữ được sinh ra bởi G sẽ có dạng : Choose one answer. a. Tập hợp các chuỗi trên bộ chữ cái {a, b} b. Tập hợp các chuỗi aiai hoặc bibi với i= 0 c. Tập hợp các chuỗi (ab)i hoặc (ba)i với i, j= 0 d. Tập hợp các chuỗi đọc xuôi và đọc ngược như nhau trên bộ chữ cái {a, b}

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: JavaScript phải có khả năng tiếp tục

Đề thi cuối kỳ - Nhóm 02 JavaScript phải có khả năng tiếp tục ! 1 Điểm : 1 Cho văn phạm G: S → aSa | bSb | ε Bằng cách dẫn xuất một số chuỗi thuộc ngôn ngữ, hãy cho biết ngôn ngữ được sinh ra bởi G sẽ có dạng : Choose one answer. a. Tập hợp các chuỗi trên bộ chữ cái {a, b} b. Tập hợp các chuỗi aiai hoặc bibi với i>= 0 c. Tập hợp các chuỗi (ab)i hoặc (ba)i với i, j>= 0 d. Tập hợp các chuỗi đọc xuôi và đọc ngược như nhau trên bộ chữ cái {a, b} 2 Điểm : 1 Cho văn phạm G: S → AAC A → SA | CC | abCA | c C → b | aA | ε Chuỗi nhập có thể được sinh ra từ văn phạm G là : Choose one answer. a. Tất cả các lựa chọn đều đúng b. abaccbb c. cc d. cabcb 3 Điểm : 1 Cho văn phạm G: S → ABC | BaD A → AB B →b | ε C →D | ε D →d Văn phạm trên chứa: Choose one answer. a. Ký hiệu vô ích, luật sinh ε b. Luật sinh ε và luật sinh đơn vị c. Luật sinh ε d. Ký hiệu vô ích, luật sinh ε và luật sinh đơn vị
4 Điểm : 1 Cho văn phạm G: S → AB A → aA | abB | aCa B → bA | ε C →ε D → dB | BC Các ký hiệu có ích trong văn phạm: Choose one answer. a. {S, A, B, C} b. {S, B, C, D} c. {A, B, C, D} d. {S, A, D} 5 Điểm : 1 Cho văn phạm G: B → begin SL end S → while E do S end | repeat S until E end | return E | exit L → ; SL | ε E → id | num .. num D → 0 | 1 | .. | 9 Tập các biến được dẫn ra từ ký hiệu bắt đầu của văn phạm G là: Choose one answer. a. {S, E, L} b. {B, S, L, E} c. {S, E, L, D} d. {B, S, L, E, D} 6 Điểm : 1 Một văn phạm phi ngữ cảnh G được gọi là thỏa dạng chuẩn Greibach GNF nếu mọi luật sinh của nó có dạng : Choose one answer. a. A → aα với A là biến, a là ký hiệu kết thúc, α là một chuỗi biến rỗng b. A → Aα| b với A là biến, α, b là các chuỗi ký hiệu bất kỳ (có thể rỗng) c. A → aα với A là biến, a là ký hiệu kết thúc, α là một chuỗi biến (có thể rỗng) d. A → BC | a với A, B, C là biến, a là ký hiệu kết thúc 7 Điểm : 1
Cho văn phạm G với tập luật sinh như sau: S → AB A → Ac | a B → dB | b Bằng cách dẫn xuất một số chuỗi thuộc ngôn ngữ, hãy cho biết ngôn ngữ được sinh ra bởi G sẽ có dạng : Choose one answer. a. Tập hợp các chuỗi có dạng aicdbj với i, j >= 0 b. Tập hợp các chuỗi trên bộ chữ cái {a, b} c. Tập hợp các chuỗi có dạng acidjb với i, j >= 0 d. Tập hợp các chuỗi a(cd)ib với i >= 0 8 Điểm : 1 Cấu trúc dữ liệu được tổ chức cho bộ nhớ của một ôtômát đẩy xuống - Pushdown Automata (PDA) có dạng : Choose one answer. a. Chồng b. Hàng đợi c. Ngăn xếp d. Không có cấu trúc 9 Điểm : 1 Cho văn phạm G: S → A | Aa A→ B B → Cb | b C → D | ab D→ b ΔA = ? Choose one answer. a. {A, B, C, D, S} b. {A, B} c. {A, B, C, D} d. {A, B, C} 10 Điểm : 1 Cho văn phạm G: S → AB A → aA | abB | aCa B → bA | BB | ε C →ε D → dB | BCB
Tập các biến rỗng Nullable trong văn phạm là: Choose one answer. a. {A, B, C, D} b. {S, A, B, C, D} c. {B, C, D} d. {S, B, C, D} 11 Điểm : 1 Cho văn phạm G: S → [E] | E E →E + T | E – T | T T →T * F | T / F | F F → (E) | D | ε D → 0 | 1 | .. | 9 Tập các ký hiệu kết thúc của G là: Choose one answer. a. Không có lựa chọn nào đúng b. T = {+, - , *, /, [ ], 0, 1, .., 9, (, ), ε} c. T = {+, - , *, /, [ ], 0, 1, .., 9, ( ), ε} d. T = {0, 1, .., 9, ε} 12 Điểm : 1 Cho văn phạm G: S → A | Aa | a A→ B B → Cb | c C → D | abc D→ b ΔS = ? Choose one answer. a. {S, A, B} b. {S, A} c. {S, A, B, C} d. {S, A, B, C, D} 13 Điểm : 1 Cho văn phạm G: S → CAab | ASS | Aa | C A → aA | ACa | acc B → bBD | Bb | c C → bAS | CC | ε D → DD Tập các biến có thể sinh ra được chuỗi ký hiệu kết thúc trong văn phạm G là : Choose one answer.
a. {A, B, C, D} b. {A, B, C, S} c. {A, B, C} d. {S, A, B, D} 14 Điểm : 1 Cho văn phạm G: E →E + T | T T →T * F | F F → a | (E) Dẫn xuất trái nhất cho chuỗi a + a * a là: Choose one answer. a. E => E + T => E + T * F => E + T * a => E + F * a => E + a * a => T + a * a => F + a * a => a + a * a b. E => E + T => E + T * F => T + T * F => F + T * F => a + T * F => a + T * a => a + F * a => a + a * a c. E => E + T => E + T * F => T + T * F => T + T * a => F + T * a => a + T * a => a + F * a => a + a * a d. E => E + T => T + T => F + T => a + T => a + T * F => a + F * F => a + a * F => a + a * a 15 Điểm : 1 Cho văn phạm G: S → 0S1 | 01 Văn phạm G’ tương đương G có dạng chuẩn Chomsky CNF là : Choose one answer. a. S → C0D | 01 C0→ 0 ; C1 → 1; D → SC1 b. S → C0D | C0C1 C0→ 0 ; C1 →1; D → SC1 c. Không có lựa chọn nào là đúng d. S → C0D1 | D2 C0→ 0 ; C1 → 1; D1→ SC1 ; D2→ C0C1 16 Điểm : 1 Cho văn phạm G: S → aSbS | bSaS | ε Chuỗi dẫn xuất phải nhất từ văn phạm G sinh ra câu nhập abab là : Choose one answer. a. S => aSbS => aSbaSbS => aSbabS => ababS =>abab b. S => aSbS => abSaSbS => abSabS => abSab =>abab c. S => aSbS => aSbaSbS => aSbaSb => aSbab =>abab d. S => aSbS => abSaSbS => abaSbS => ababS =>abab 17 Điểm : 1 Cho văn phạm G: S → aB A → bcCCC | dA
B →e C → fA D → Dgh Tập các biến vô ích của văn phạm: Choose one answer. a. {A, B, C, D} b. {A, B, D} c. {B, C, D} d. {A, C, D} 18 Điểm : 1 Cho văn phạm G: S → aBC A → aA | abB | aCa B → bA | BD | ε C →ε D → d | BCB Tập các biến rỗng (Nullable) trong văn phạm G là : Choose one answer. a. {B, C, S} b. {B, C, D} c. {B, C, D, S} d. {B, C} 19 Điểm : 1 Cho văn phạm G: S → CAab | ASS | Aa | C A → aA | ACa | acc B → bBD | Bb | c C → bAS | CC | ε D → DD Tập các biến vô ích trong văn phạm G là : Choose one answer. a. {D, B, C} b. Không có biến nào vô ích c. {D} d. {B, D} 20 Điểm : 1 Cho văn phạm phi ngữ cảnh G, các cây dẫn xuất được sinh từ những chuỗi dẫn xuất khác nhau cho cùng một chuỗi nhập là : Choose one answer.
a. Những cây dẫn xuất hoàn toàn khác nhau b. Chỉ có những nút lá trên cây là giống nhau c. Những cây dẫn xuất hoàn toàn giống nhau d. Những cây dẫn xuất gần giống nhau 21 Điểm : 1 Cho văn phạm G: S → AB A → SAA | BB | bB | ε B → b | aA Văn phạm G’ tương đương G không có chứa luật sinh ε là : Choose one answer. a. S→ AB | B A→ SAA | SA | S | BB | bB | ε B→ b | aA | a b. S→ AB | B A→ SAA | SA | S | BB | bB B→ b | aA | a c. Không có lựa chọn nào là đúng S → AB | B | A A→ SAA | SA | S | BB | B | bB B→ b | aA | a d. 22 Điểm : 1 Theo hệ thống phân cấp trên văn phạm của Noam Chomsky, văn phạm phi ngữ cảnh thuộc lớp : Choose one answer. a. Văn phạm loại 2 b. Văn phạm loại 3 c. Văn phạm loại 1 d. Văn phạm loại 0 23 Điểm : 1 Một văn phạm phi ngữ cảnh được gọi là văn phạm mơ hồ nếu có thể vẽ nhiều hơn một cây dẫn xuất khác nhau cho cùng một chuỗi nhập. Đáp án : Đúng Sai 24 Điểm : 1 Nếu G (V, T, P, S) là một văn phạm phi ngữ cảnh thì S ⇒* α khi và chỉ khi có tồn tại một cây dẫn xuất trong văn phạm sinh ra α. Đáp án :
Đúng Sai 25 Điểm : 1 Cho văn phạm G: B → begin SL end S → while E do S end | return E | exit L → ; SL | F eof | ε E → id | num .. num F → FD | F D →0 | 1 Các thành phần của văn phạm phi ngữ cảnh được cho bởi văn phạm G là: Choose one answer. a. G({B, S, L, E, F, D}, {begin, end, while, do, return, exit, ; , eof, id, num, ‘.. ‘, ε, 0, 1}, P, B) b. G({B, S, L, E, F, D}, {begin, end, while, do, return, exit, ; , eof, id, num, ‘.. ‘, 0, 1}, P, B) c. G({B, S, L, E, F, D}, {begin, end, while, do, return, exit, ; , eof, id, num, ‘.. ‘, ε, 0, 1}, P, S) d. Không có lựa chọn nào đúng Thời gian còn lại Đáp án: 1. d 2. a 3. d 4. a 5. b 6. c 7. c 8. c
9. b 10. c 11. a 12. a 13. b 14. d 15. b 16. c 17. d 18. b 19. d 20. c 21. b 22. a 23. dung 24. dung 25. d