ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 61

В автомате с выталкиванием P = (Q, Σ, Γ, δ, q0, F) переход вида

где p,q∈Q, a∈σ∪{ϵ}, X,Y,∈Γ∪{ϵ}, представляет

(q,Y) ∈ δ(p,a,X) 

Рассмотрим следующий автомат выталкивания по входному алфавиту Σ={a,b} и стековому алфавиту Γ={#,A}.

Количество строк длины 100, принятых вышеописанным автоматом с выталкиванием вниз, равно ___________ .
(А) 50
(Б) 100
(С) 55
(Д) 45

Ответ: (А)
Объяснение: Согласно заданному вопросу,

L = {anbm| n>m & n+m=100}
L = a51b49,…..,a99b,a100
|L| = 50 

Для достижения q3 из q2 на вершине стека должно быть «A», следовательно, n>m.
Тест на этот вопрос