Câu hỏi trắc nghiệm về tính đệ quy

Câu 1 Ngôn ngữ L = {an

b

m

| n> m} Văn phạm nào sau đây sinh ra ngôn ngữ L

A) S → aSb|a

B) S → aSb|aS|a

C) S → aSb|aS| ε

D) S → aSb| SS|a

Đáp án B

Câu 2 Ngôn ngữ L = {an

b

m

| n<> m} Văn phạm nào sau đây sinh ra ngôn ngữ

L

A) S → A|B; A → aA| aX; B → Bb|Xb; X → aXb| ε

B) S → A|B; A → aAb| a; B → aAb|b

C) S → aS|Sb| ε

D) Cả 3 văn phạm trên đều sinh ra

Đáp án A

Câu 3 Cho văn phạm G = {S → aSb|bSa|SS|a|ε} ∑ = {a, b } ∆= {S} G sinh ra

ngôn ngữ nào sau đây: (wR

là xâu ngược của xâu w)

A) {wwR

| w ∈ {a,b}*}

B) {w ∈ {a,b}*| số kí tự của a >= số kí tự của b trong xâu w }

C) {wxwR

| x ∈ {a, b, ε}, w ∈ {a,b}*}

D) {w ∈ {a,b}*| số kí tự của a = số kí tự của b trong xâu w }

Đáp án B

Câu 4 Cho văn phạm G = {S → aSb|bSa|SS|a|ε} ∑ = {a, b } ∆= {S} G sinh ra

ngôn ngữ nào sau đây: (wR

là xâu ngược của xâu w)

A) {wwR

| w ∈ {a,b}*}

B) {w ∈ {a,b}*| số kí tự của a >= số kí tự của b trong xâu w }

C) {w ∈ {a,b}*| số kí tự của a = số kí tự của b trong xâu w }

D) {w | w ∈ {a,b}* và w = wR

}

Đáp án B

Câu 5 Cho văn phạm G = {S → aSa|bSb|a|b|ε} ∑ = {a, b } ∆= {S} Tìm ngôn

ngữ tương ứng với ngôn ngữ do G sinh ra:

A) {a2nb

n

| n≥ 0}

B) {an

b

n

|n ≥ m}

C) {an

b

n

|n ≠ m}

D) { an

b

n

| n≥ 0, m≥ 0, m ≤ n ≤ 2m}

Đáp án B

Câu 6 Cho văn phạm G = {S → aSbS|bSaS|a|ε} ∑ = {a, b } ∆= {S} . Văn

phạm G nhập nhằng trên chuỗi nào sau đây:

A) aaba

B) aab

C) aaabb

D) tất cả đều sai

Đáp án D

Câu 7 Văn phạm nào sau đây KHÔNG nhập nhằng:

A) S→ aSb|bSa|SS|a