Все мы знаем, что (a + b)* — это обычный язык, содержащий только символы a и b. Но (a + b)* — это строка бесконечной длины, и она регулярна, поскольку мы можем построить конечные автоматы, поэтому она должна быть конечной.
Кто-нибудь может объяснить это?
Конечный автомат можно построить для любого регулярного языка, а регулярный язык может быть конечным или бесконечным множеством. Конечно, существуют бесконечные множества, которые не являются не обычными множествами. Посмотрите на диаграмму Венна ниже:
Примечания:
1. каждое конечное множество является регулярным множеством.
2. любой dfa для бесконечного множества всегда будет содержать цикл (или dfa без цикла невозможен для бесконечного множества).
3. каждый нерегулярный язык является бесконечным множеством .
Слово «конечный» в конечных автоматах означает наличие «конечного объема памяти» в автоматах для класса обычных языков, следовательно, только «конечный» (или говорит ограниченный) объем информации может храниться в любой момент времени во время обработки. строка языка.
В конечных автоматах память присутствует только в виде состояний (тогда как в другом классе автоматов, таких как Pda, внешняя память машины Тьюринга используется для хранения неограниченной информации). Вы можете думать о конечных автоматах как о ЦП без явной памяти; который может хранить в своих регистрах только последние результаты.
Таким образом, мы можем определить «обычный язык» как класс языков, для которых требуется хранить только ограниченную (конечную) информацию в любой момент времени при обработке языковых строк.
Далее читайте (для бесконечных языков):
a*b* является обычным? Но язык { anbn | n > 0 } не является обычным языкомКаждое слово в языке (a+b) имеет конечную длину. Точно так же, как существует бесконечно много целых чисел, но каждое из них конечно.
Да, сам язык представляет собой бесконечное множество. Большинство языков. Но конечный автомат (NB: автоматы во множественном числе) прекрасно работает для них, при условии, что каждое слово имеет конечную длину.
В качестве отступления: этот тип вопроса, вероятно, следует отправлять на cs.stackexchange.com.
Но
(a + b)*— это строка бесконечной длины.
Нет, (a + b)* — это конечный способ выразить бесконечный набор (язык) конечных строк.
1. Регулярное выражение описывает строку, сгенерированную некоторым языком. Применение этого регулярного выражения дает вам все строки, которые могут быть описаны этим языком.
2. Когда вы конвертируете это регулярное выражение в конечный автомат (автоматы с конечными состояниями), это означает, что те же самые строки могут быть сгенерированы путем перехода от одного состояния к другому. состояние на этом автомате. Теперь интуитивно понятно, что каждое состояние здесь представляет группу строк, принадлежащих этому языку. В нем говорится, что после «поглощения» некоторого ввода строка теперь находится в состоянии X.
Пример:
Если вы хотите, чтобы регулярное выражение принимало строки с четным числом 0 , тогда у вас будет одно состояние (группа), указывающее, что четное число 0 наблюдалось в ввод до сих пор. И еще одно состояние (группа) для нечетных чисел --> это состояние будет вашим неприемлемым состоянием в FA.
Как показано здесь, вам просто нужно 2 (конечных) состояния для генерации бесконечного числа строк из-за группировки нечетных и четных, которые мы сделали.
И именно поэтому это регулярно.
Это просто означает, что существует конечное регулярное выражение для указанного языка и оно нигде не связано ни с одной из строк, сгенерированных из выражения. Для многих регулярных языков мы можем сгенерировать бесконечное количество строк, которые следуют этому языку, но этот язык является регулярным, чтобы доказать, что нам нужно регулярное выражение, которое должно быть конечным. Таким образом, здесь выражение (a+b)* является конечным способом выражения 0-n числа a или b или их комбинации, но n может принимать любое значение, что приводит к бесконечному количеству нет. строк.
