Регулярные выражения

Question

Прежде всего, я не знаю, является ли это правильным переводом того, что я прошу.

На одном из моих курсов мы просто изучали регулярные выражения, формальные языки и так далее.

Alphabet {1,0,S,R}
Terminals {1,0}
Rules:

S ::= 0
S ::= 1
S ::= 1R
R ::= 1R
R ::= 0R
R ::= 1
R ::= 0

В этом случае, допустим, я начинаю с 1R, а затем могу продолжать с 1R или 0R.

Если я начну с 1R, то просто 1.... тогда предложение (в данном случае его двоичные числа) является полным, верно?Поскольку я не могу «добавить» что-либо потом, скажем, 1R, затем я выбираю 1, а затем снова выбираю 1R?

Заранее спасибо, и, пожалуйста, поменяйте / переместите сообщение, если оно некорректно.

ДОБАВЛЕНО:

0  at rule S ::= 0  
1  with S ::= 1  
10 with S ::= 1R, so R ::= 0

Как сгенерировать 1100110?

Это не домашняя работа, это пример / вопрос от powerpoint.Я не понимаю, как это делается.

Answer 1

То, что у вас есть, это обычный язык, определенный с помощью контекстно-свободной грамматики. Регулярное выражение, которое определяет тот же язык: (0)U(1{0,1}*). В простом английском языке обычный язык содержит все строки 0 и 1, которые начинаются с 1, и строку 0.

Контекстно-свободная грамматика начинается с некоторого начального нетерминального символа, в данном случае это кажется S. Затем вы можете заменить любые нетерминальные символы на строку символов в соответствии с перечисленными правилами производства. Это делается, когда строка не содержит нетерминальных символов.

В вашем примере вы можете "выбрать 1R", только если в строке в настоящий момент есть S или R для замены. Как и в случае с этой грамматикой, когда вы в первый раз заменяете R на 1, у вас больше нет никаких нетерминалов для замены, и создание строки завершено.

Редактировать: Вот след производства 1100110.

S  
1R         via S ::= 1R
11R        via R ::= 1R
110R       via R ::= 0R
1100R      via R ::= 0R
11001R     via R ::= 1R
110011R    via R ::= 1R
1100110    via R ::= 0

Answer 2

Вы правы. Добавление не допускается, только замена. Однако с этим языком вы можете непрерывно увеличивать длину строки, выбирая «R :: = 1R» или «R :: = 0R», а затем снова подставляя R.

Answer 3

Если я начну с 1R, то просто с 1 .... тогда предложение (в данном случае его двоичные числа) является полным, верно?

Да, это правильно.Предложение 11 соответствует S = 1R = 11.

Однако с помощью этой грамматики вы всегда можете использовать R = 1R или R = 0R, чтобы добавить все больше и больше цифр в ваше предложение.

Изменить: В ответ на вопрос изменить:

Как сгенерировать 1100110?

1100110 = S = 1R =11R = 110R = 1100R = 11001R = 110011R = 1100110

Надежда, которая поможет вам понять.

Удачи!