YarikBlyat1
unknown
python
2 years ago
2.8 kB
5
Indexable
# МП-распознаватель для грамматики 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
Editor is loading...