YarikBlyat1

# МП-распознаватель для грамматики L = {1^n0^(4n)} ∪ {0^n1^(3n)} ∪ {0^n(10)^n}

def mp_recognizer(s):
    stack = ['S', '$']  # начальный стек
    i = 0  # индекс текущего символа в строке s
    
    while len(stack) > 1:  # пока стек не опустеет до символа '$'
        top = stack[-1]  # верхний символ стека
        
        if top.isupper():  # если верхний символ - нетерминальный
            if top == 'S':
                if s[i] == '1':
                    stack.pop()
                    stack.extend(reversed('AA0A1S$'))
                elif s[i] == '0':
                    stack.pop()
                    stack.extend(reversed('BB1B0S$'))
                elif s[i] == '':  # конец строки
                    stack.pop()
                else:
                    return False  # строка не принадлежит языку
            elif top == 'A':
                if s[i] == '1':
                    stack.pop()
                    stack.extend(reversed('AA0A1'))
                    i += 1
               elif top == '0':
                    stack.pop()
                    stack.extend(reversed('ε'))
                else:
                    return False
            elif top == 'B':
                if s[i] == '0':
                    stack.pop()
                    stack.extend(reversed('BB1B'))
                    i += 1
                elif s[i] == '':  # конец строки
                    stack.pop()
                else:
                    return False
            elif top == 'C':
                if s[i] == '0':
                    stack.pop()
                    stack.extend(reversed('CX'))
                    i += 1
                elif s[i] == '':  # конец строки
                    stack.pop()
                else:
                    return False
            elif top == 'X':
                if s[i:i+2] == '10':
                    stack.pop()
                    stack.extend(reversed('ε'))
                    i += 2
                else:
                    return False
        else:  # если верхний символ - терминальный
            if top == s[i]:
                stack.pop()
                i += 1
            else:
                return False  # строка не принадлежит языку
    
    return True if i == len(s) else False  # если строка была полностью прочитана, то она принадлежит языку

# Пример использования
print(mp_recognizer('11110000'))  # True
print(mp_recognizer('000111'))  # True
print(mp_recognizer('001010'))  # True
print(mp_recognizer('1101'))  # False