Đ 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 aậ ợ ỗ iai ho c bặibi 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 aậ ợ ỗ ạ icdbj 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 acậ ợ ỗ ạ idjb 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