Как и в теме, если у меня есть язык с алфавитом {a}, то a^n, где n> 1000 - обычный язык? Я запутался. Я попытался применить здесь Pumping Lemma, и я не уверен в этом. С одной стороны я вижу, что если я выкачу из 1001 одного из а, то у меня будет^1000, который не принадлежит L. С другой стороны, я не мог найти примеров таких случаев, поэтому, возможно, мои рассуждения ошибочны.Является ли n n, где n> 1000 - обычный язык?
Это регулярно. Рассмотрим регулярное выражение a{1001}a*, где a{1001} представляет собой строку из 1001 a.
Спасибо. Что относительно (аа) *. Это тоже регулярно? Я могу перекачать его для строки, то есть aaaa с i = 1, и я получу aaaaa, который не принадлежит языку. Я здесь? –
'(aa) *' явно регулярный, вы просто описали его с регулярным выражением. Эквивалентный FSM 3-го состояния найти не сложно. – Charles
Хорошо, я должен прочитать больше о reg. языков и перекачки леммы. Еще раз спасибо :) –
этот вопрос непонятный. Вы можете использовать http://cs.stackexchange.com/ – ergonaut