Является ли *b* регулярным?

Question

Я знаю, что ^{n n} b для n > 0 не является регулярным по лемме прокачки, но я бы вообразил a*b* быть регулярным, поскольку оба a,b не обязательно должны быть одинаковой длины. Есть ли доказательства того, что это регулярно или нет?

Answer 1

Ответ на ваш вопрос:

представьте, что * b * является регулярным, есть ли доказательства того, что оно регулярное или нет?

Не нужно представлять, выражение a*b* называется регулярным выражением (re), а регулярные выражения возможны только для регулярных языков. Если язык не является регулярным, то регулярное выражение также невозможно для этого, и если язык является регулярным языком, то мы всегда можем представить его с помощью некоторого регулярного выражения.

Да, a*b* представляет собой обычный язык.

Описание языка: любое количество a с последующим любым числом b (под любым числом я имею в виду ноль (включая ноль ^) или больше раз). Некоторые примеры строк:

{^, a, b, aab, abbb, aabbb, ...}

DFA для RE a*b* будет следующим:

      a-            b-
      ||            ||
      ▼|            ▼|
---►((Q0))---b---►((Q1))

In figure: `(())` means final state, so both `{Q0, Q1}` are final states.

Вам необходимо понять следующую основную концепцию:

Что такое в основном обычный язык? И почему бесконечный язык `a*b*` является регулярным, тогда как такие языки, как `{a <sup>n</sup> b <sup>n</sup> | n> 0} `не являются регулярными!!

Язык (набор) называется обычным языком, если ему требуется только ограниченное (конечное) количество информации для хранения в любой момент времени при обработке строк языка.

Итак, что такое "ограниченная" информация?
Например: рассмотрите возможность включения / выключения вентилятора. Просматривая переключатель вентилятора, мы можем сказать, включен ли вентилятор on или же off состояние (это ограниченная или ограниченная информация). Но мы не можем сказать, что "сколько раз" вентилятор был включен и выключен в прошлом! (для запоминания требуется механизм хранения "неограниченного" количества информации для подсчета - "сколько раз", например, какой-то счетчик расхода используется в наших автомобилях / мотоциклах).

Язык {a ⁿ b ⁿ | n> 0} не является обычным языком, потому что здесь n неограничен (это может быть бесконечно большим). Чтобы проверить строки на языке a ⁿ b ⁿ, нам нужно запомнить, сколько a символы пришли, и это требует бесконечной памяти для подсчета, потому что количество a символы в строке могут быть бесконечно большими!

Это означает, что автомат способен обрабатывать строки языка a ⁿ b ^{n, только} если у него бесконечная память, например, PDA.

В то время как, a*b* конечно, регулярна по своей природе, потому что есть ограниченное ограничение - это b может прийти после некоторого a (а также a не может прийти после b). И именно поэтому каждая строка этого языка может быть легко обработана (или распознана) автоматами, в которых у нас конечная память, а конечные автоматы - это класс автоматов, в которых память конечна. Да, в конечных автоматах у нас есть конечный объем памяти в терминах состояний.

(Память в конечных автоматах присутствует в виде состояний Q и согласно принципу автоматов: любые автоматы могут иметь только конечные состояния. следовательно, конечные автоматы имеют конечную память, поэтому класс автоматов для регулярных языков называется конечными автоматами. Вы можете представить себе конечный автомат, такой как CPU без памяти, который имеет конечный регистр для запоминания своих внутренних состояний)

Конечное состояние ⇒ Конечная память ⇒ Может быть обработан только язык, для которого конечная память должна храниться в любой момент времени при обработке строки ⇒ этот язык называется Regular Language

Отсутствие внешней памяти является ограничением конечного автомата ⇒ или, можно сказать, ограничением конечного автомата определенного класса языка, называемого Regular Language.

Вам следует прочитать другой ответ "Конечность обычного языка", чтобы изучить сферу применения обычного языка.

примечание стороны:

• язык {a ⁿ b ⁿ | n> 0} является подмножеством a*b*
• Также язык {a ⁿ b ⁿ | 10 ^{> 100} n> 0} регулярный, большой набор, но регулярный, потому что n ограничен, следовательно, для этого языка возможны конечные автоматы и регулярные выражения.

Вы должны также прочитать: Как доказать, что язык является регулярным?

Answer 2

Доказательство: ((a*)(b*)) является правильно сформированным регулярным выражением, следовательно, соответствует регулярному языку. a*b* является синтаксическим сокращением того же выражения.

Еще одно доказательство: обычные языки закрыты для объединения. а * это обычный язык. b* является регулярным языком, поэтому их конкатенация a*b* также является регулярным выражением.

Вы можете построить автомат для этого:

0 ->(a) 1
0 ->(b) 2
1 ->(a) 1
1 ->(b) 2
2 ->(b) 2
2 ->(a) 3
3 ->(a,b) 3

где только 3 не является принимающим состоянием, и докажите, что язык является *b*.

Answer 3

Чтобы доказать, что язык является регулярным, достаточно показать либо:

1) Существует некоторое DFA, которое распознает это. В этом случае DFA тривиален.

2) Язык может быть выражен как регулярное выражение, как упомянуто в другом ответе. a*b* это регулярное выражение для распознавания этого языка.

Answer 4

Обычный язык - это язык, который может быть выражен с помощью регулярного выражения или детерминированного или недетерминированного конечного автомата или конечного автомата. Язык - это набор строк, которые состоят из символов определенного алфавита или набора символов. Обычные языки являются подмножеством набора всех строк.

Свойство замыкания - это утверждение о том, что определенная операция над языками при применении к языкам в классе (например, к обычным языкам) дает результат, который также находится в этом классе.

этот RE показывает.. тип языка, который принимает несколько из (а), если таковые имеются, но до (б)

означает язык без какой-либо подстроки (ba)

Answer 5

Обычные языки не являются подмножеством контекстно-свободных языков. Например, ab является обычным, состоящим из всех строк, состоящих из подстроки a, за которой следует подстрока b. Это не подмножество a^nb^n, а надмножество.