formal-languages

3зной

2ответ

Как написать краткое регулярное выражение для всех строк, содержащих «a», «b» и «c», но не более 2 «b» и 3 «c» s

Я совсем недавно начал учиться регулярному выражения и пытался написать один для вопроса выше. Было бы непросто, если бы ограничения были помещены только на одну букву (например, не более 2 "b" s). То

0зной

1ответ

Почему эта грамматика не чувствительна к контексту?

Я получил эту грамматику: G = (N, Epsilon, P, S) с N = {S, A, B} Epsilon = {a}, P: S -> e S -> ABA AB -> aa aA -> aaaA A -> a Почему это грамматика только типа 0? Я д

1зной

2ответ

Как определить число состояний конечных автоматов по любому языку?

У меня жгучий вопрос о конечных автоматах, как мы можем знать, что этот язык нуждается в 2 состояниях или 3 состояниях? Я имею в виду, есть ли какая-нибудь формула для этого? Хотя я считаю, что мы все

6зной

1ответ

Как реализовать групповые символы, классы символов, классы отрицательных символов и т. Д. В модели для регулярной грамматики?

TL; DR: Как вычислительная модель моделирует произведения грамматики, так что существует неопределенное количество продуктов для одной и той же левой стороны? Я работаю над проектом в отношении теории

-1зной

1ответ

Предоставьте бесплатные граммы для грампластинок на следующих языках:

a) L = {1^i - 1^j = 1^(i-j) | i-j>=0, i,j>=0} b) L = {a^i b^j c^k | k!=i+j, i,j,k>=0 Я не могу понять, как реализовать эти процедуры. Я понимаю концепцию, я просто не могу ее обработать. Любая помо

0зной

1ответ

Смутно о классах сложности?

Моя книга использует это определение для полиномиального класса сложности (L представляет собой бинарный язык): Но по этому определению, не все языки принадлежат к классу полиномиальной сложности? Пос