Кто может помочь с дискрой?

bonita562

Докажите, что язык {ambmck | k > m} не кс-язык.
2. Используя лемму о разрастании для регулярных языков, докажите
нерегулярность
языка { amban| m > n > 0 } в алфавите {a, b}*
3. Какой язык порождает грамматика
S -> bSSS | a ?
Как решаются такие задачки. Посоветуйте литературу или помогите с решением.

angelochek

Лень думать, но первое, по-видимому, решается с помощью pumping lemma (лемма о разрастании для КС-языков). Можешь посмотреть книгу Пентуса и Пентус "Теория формальных языков".

angelochek

По поводу третьего - что значит какой язык?
Грамматика, я так понимаю, -
S -> bSSS, S -> a. Да?

sasha_m

3. Какой язык порождает грамматика
S -> bSSS | a ?

Язык:
(b^na^m)
n = [0,1,2...]
m= 2k+1, при к=0...
Помойму так.
Оставить комментарий
Имя или ник:
Комментарий: