Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 88

GATE

Рассмотрим следующую грамматику G:

S → bS | aA | b
A → bA | aB
B → bB | aS | a

Пусть Na (w) и Nb (w) обозначают число a и b в строке w соответственно. Язык L (G) ⊆ {a, b} +, порожденный G,
(A) {w | Na (w)> 3Nb (w)}
(B) {w | Nb (w)> 3Nb (w)}
(C) {w | Na (w) = 3k, k ∈ {0, 1, 2,…}}
(D) {ш | Nb (w) = 3k, k ∈ {0, 1, 2,…}}

Ответ: (с)
Пояснение: здесь мы имеем

S → bS
S → baA	     (S → aA)
S → baaB     (A → aB)
S → baaa     (B → a)

Следовательно, | Na (w) | = 3

Кроме того, если мы используем A → bA вместо A → aB,

S → baA
S → babA

Чтобы завершить A, мы должны будем использовать A → aB, так как только B заканчивается в a (B → a).

S → baA
S → babA
S → babaB
S → babaa

Таким образом, здесь также, | Na (w) | = 3

Таким образом, C является правильным выбором.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 88

0.00 (0%) 0 votes