Создайте регулярное выражение для определения обычного языка

Язык представляет собой бесконечное множество цепочек, которые определяются следующими условиями.

Условия:

1) The language chains may consist of symbols from the set {1,a,b}. 
2) The language chains always start from subchain '1a'.
3) Every languange chain has to include at least one subchain 'aa'.

Например:

1aa, 1abaa, 1aaab, 1aab1a, ... etc.

Мое решение:

1a (1+a+b)* a (1+a+b)*

Но я не совсем уверен, что это правильно. Это правильно?


regex regular-language
person Happy Torturer    schedule 14.05.2014    source источник
comment
Кроме того, но мне это не кажется обычной грамматикой ;-)   -  person Felix Frank    schedule 14.05.2014
comment
Этот вопрос кажется не по теме, потому что он относится к cs.stackexchange.com.   -  person Barmar    schedule 14.05.2014

Ответы (2)


arrow_upward
3
arrow_downward

Ваше решение аннулирует условие 3. Оно обеспечит только a подцепь. Например, он будет соответствовать 1abab, который не содержит aa. Вот один из них, который я нашел работающим:

1a(a[1ab]*|[1ab]*aa[1ab]*)

Это начинается с 1а. Затем в зависимости от того, является ли следующий символ a (как в 1aa, который удовлетворяет всем трем условиям, кстати), ищет любую комбинацию 1, a и b или любую комбинацию с aa в ней.

Примечание. В вашей нотации формального языка данное регулярное выражение будет выглядеть так:

1a((a(1+a+b)*)+((1+a+b)*aa(1+a+b)*))

person Akash    schedule 14.05.2014
comment
Но 1аа не соответствует этому. - person Felix Frank; 14.05.2014
comment
@FelixFrank Спасибо. Я улучшу регулярное выражение. - person Akash; 14.05.2014
comment
Почему? (1+a+b)* также может быть пустым символом или «лямбдой». Я имею в виду: 1a NULL NULL или 1aa - person Happy Torturer; 14.05.2014
comment
@ user3470412 конечно. Но это также может быть не ни тем, ни другим. Как я уже сказал, ваше регулярное выражение будет соответствовать 1abab, что аннулирует условие 3. Вам нужно создать регулярное выражение, которое не будет соответствовать ничему, кроме того, что удовлетворяет всем трем условиям. - person Akash; 14.05.2014
comment
Но как написать свое решение в том виде, который я предложил? Поскольку такие операции, как '|' не допускаются, и у меня нет инструментов для проверки правильности моих решений. - person Happy Torturer; 14.05.2014
comment
Благодарю вас! Попробую вникнуть в суть этого решения. - person Happy Torturer; 14.05.2014
comment
Можно ли как-то избавиться от тех скобок (), которые стоят без символа бесконечной итерации Клини * рядом с ними? В моей теории есть только один пример, и он использует только ()*. Позвольте мне написать этот пример здесь. Язык определяется набором {0,1,a,b}*. Условия: (1) Все цепочки должны заканчиваться на «01a»; (2) Все цепочки должны включать только четное количество символов «а». Пример: а01а, аб01а, ааа01а. Правильное решение будет таким: ((0+1+b)*a(0+1+b)*a(0+1+b)*)*(0+1+b)*a(0+1+ б)*01а. Он содержит только скобки итерации ()*, но не скобки приоритета (). - person Happy Torturer; 14.05.2014
comment
Я думаю, что это решение для моей проблемы тоже может быть правильным: 1a (a (1+b)*)* a ((1+b)* a)*. - person Happy Torturer; 14.05.2014
comment
Но не включает 1abaa. - person Felix Frank; 14.05.2014
comment
Может быть, этот будет правильным? 1a ((1+b)* a)* (a (1+b)*)* a (1+b+a)* Это решение разрешит 1abaa и проигнорирует такие вещи, как: 1aba, 1abab. - person Happy Torturer; 15.05.2014

arrow_upward
0
arrow_downward

Я считаю, что вы не можете сформировать одно регулярное выражение, которое будет соответствовать всем и только тем строкам, которые соответствуют вашим критериям.

person Felix Frank    schedule 14.05.2014
comment
1a(a[1ab]*|[1ab]*aa[1ab]*) Я думаю, что это безупречно. - person Akash; 14.05.2014
comment
Ооо, считай, моя шляпа снята :-) - person Felix Frank; 14.05.2014
comment
Но как написать свое решение в том виде, который я предложил? Поскольку такие операции, как '|' не допускаются, и у меня нет инструментов для проверки правильности моих решений. - person Happy Torturer; 14.05.2014