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