Если язык L не является регулярным, является ли L* регулярным?
Имеет смысл предположить, что L* не регулярно. Тем не менее, я не могу найти доказательства того или иного заключения.
4 ответа
Предположим, что L - любой язык над алфавитом Σ. Если L не регулярно, то и L+Σ, но (L+Σ)∗=Σ∗ регулярно. Таким образом, вы можете видеть, что L* не всегда не регулярно.
Предполагать
L={a^n , n=k! , k>=1}. Как вы знаете, этот язык не является регулярным. Но
L*={a^m, m>=0} or L*(r)=a*,L* — регулярный язык. Так что это предложение не всегда верно.
Если L нерегулярен, L* может быть как регулярным, так и нерегулярным, в зависимости от языка L.
Пусть L — язык {a^p | p — простое число}. L* содержит все строки длины два и выше, поскольку содержит все линейные комбинации строк aa и aaa. L* является регулярным, так как это разность множеств регулярных языков a* и {a}, а обычные языки закрыты относительно разности множеств.
Пусть L = {a^nb^n | п > 0}. Строка в L* длины не менее p (где p — длина накачки из леммы о накачке) — это a^pb^p. Накачка может изменить только количество букв а и не может дать нам другую строку в языке, поэтому L* не является правильным.
Обратите внимание на интересный факт: L* всегда регулярен, если L — язык над алфавитом, содержащий только один символ. Первый пример, который я привел, иллюстрирует, почему так должно быть всегда.
Не обязательно, но возможно. Скажем, L равен 0, 1, 01, 0011, 000111, 00001111 и т. Д. L не является регулярным, но L* является просто [01]*,