Регулярное выражение. Обычный или Нерегулярный?

Question

Я просто хочу получить второе мнение об этих выражениях и о том, являются ли они неправильными или регулярными.

{0^n 1^m | n >= m >=0} РЕГУЛЯР

{0^n 1^m | n,m >=0}* РЕГУЛЯР

{0^n 0^n | n>=0} НЕРЕГУЛЯРНО

Кто-нибудь может подтвердить, что это правда?

Answer 1

{0^n 1^m | n >= m >=0} Поскольку FSM не может отслеживать, что n было, чтобы обеспечить n> = m, FSM не может представлять выражение.

{0^n 1^m | n,m >=0}* - может показаться, что FSM представляет это, но есть проблемы. В отличие от первой проблемы, n и m не связаны друг с другом, поэтому проблем с созданием FSM нет. Проблема в том, что n и m должны оставаться одинаковыми для нескольких проходов через машину. Опять же, поскольку памяти нет, это невозможно.

{0^n 0^n | n>=0} - это также просто для FSM. Это очень похоже на FSM второй проблемы. RE составляет (00)*