(ab+ba)* принимает все ноль или более «а», за которыми следуют ноль или более «b» s, а также ноль или более «b», а затем ноль или более «а». Что такое отказ от этого RE?Регулярные выражения
Просто подумайте о струнах, которые не принимаются (ab+ba)*.
Ну, подумайте об этом (и это важно - это Ваша домашняя работа, и вам нужно понять).
Основываясь на вашем описании (ваш фактический RE находится в очень странной форме BTW, ничего подобного RE-формату, который я использовал - на более регулярном языке RE, это было бы a*b*|b*a*), нет условия отклонения, если у вас нет неявные якоря в начале и конце строки (в этом случае aba будет отклонен).
Тот факт, что всех ваших ограничений является «ноль или больше», означает, что любая строка будет проходить.
'+' часто используется для обозначения чередования, поэтому эквивалентное выражение будет (ab | ba) * (переход по данному выражению, а не по английскому описанию). –
Несколько заметок о терминологии: Регулярные выражения не имеют состояний - отклонение, принятие или иное. (Чистые) регулярные выражения описывают регулярные языки. У обычных языков тоже нет состояний; просто строки, которые являются элементами или не-элементы языка. Можно обсудить дополнение языка: набор строк по одному и тому же алфавиту, которые не являются элементами языка. Так получилось, что дополнение обычного языка также является обычным языком. Каждый регулярный язык может быть описан конечным автоматом, и именно этот автомат отклоняет или принимает состояния.
Неправильно давать регулярное выражение, и попросить его «отвергающие государства» - может быть много автоматов, которые описывают один и тот же регулярный язык, и один будет иметь , чтобы определить, какие из этих возможностей рассматриваются ,
Я предполагаю, что вы просите некоторые описания строк, которые не на языке , указанного вашего выражение (аb + ба) *, возможно, даже регулярное выражение, которое описывает дополнения этого языка по отношению к (a + b) *.
Один подход, который вы можете попробовать, - найти DFA, который распознает этот язык, затем изменить все принимающие состояния на отклонения состояний и наоборот. Получаемый DFA распознает дополнение к исходному языку, и (с некоторой уловкой - в качестве упражнения для читателя) это можно преобразовать обратно в обычное выражение .
Хм? Что означает «отвергать состояние»? – Matchu
Ваш английский перевод регулярного выражения кажется неправильным. Его нулевые или более группы от нуля до многих строк, заканчивающихся символом a. – Akusete
@Matchu Это состояние, в котором вы не можете перейти в принимающее состояние или состояние, которое не принимается. Я видел обе интерпретации. – NullUserException