Automata: Developing Context Free Grammars

Может ли кто-нибудь дать мне мыслительный процесс, связанный с разработкой контекстной свободной грамматики? Я даю язык, где есть определенное количество 0 и определенное количество 1, но число 0 не равно числу 1. Однако 0 на первом месте, а затем 1 (что должно сделать вещи более прямолинейными). Таким образом, приемлемой строкой будет 0000111 или 01111111Automata: Developing Context Free Grammars

Я не хочу, чтобы вы просто дали мне прямой ответ или ответ на все вопросы. Просто процесс его выяснения.

источник

2013-10-09 user2853262

«Дайте мне мыслительный процесс, связанный с разработкой контекстной свободной грамматики»: я предложил некоторые трюки здесь: [Советы по созданию свободной грамматики контекста] (http://stackoverflow.com/questions/15126824/tips-for-creating -context-free-grammar/15130451 # 15130451) –

Очень полезно @GrijeshChauhan .. Спасибо – user2853262

, тогда вам также нравится читать [это «Грамматика в основах официальных языков»] (http://stackoverflow.com/questions/15989197/why «Необходимость для терминалов-это-мое-решение-достаточное-достаточное»/15989998 # 15989998) –

Ну, прямой ответ, который вы не хотите, это:

S - initial symbol 
S -> X | Y 
X -> 0X1 | X1 | 1 
Y -> 0Y1 | 0Y | 0

Это первое, что приходит на ум, так что не слишком много процесса. Во всяком случае, я бы сказал, что самое первое, что вы должны увидеть, это то, что есть две возможности: либо у вас есть больше, либо нулей, и хорошо, что два делят проблему на эти два (поскольку я разделил S на X и Y).

Затем вы видите, что «контекст бесплатно» не позволяет контролировать число в любом месте, кроме границы между нулями и единицами. Вы просто получаете идею и записываете решение.

источник

2013-10-09 19:38:52

Спасибо, это помогло немного разобраться. Как вы позволите грамматике принять пустую строку? @Bartosz Marcinkowski – user2853262

Этого не должно быть, потому что пустая строка имеет такое же количество нулей и единиц. –

ответ

Смежные вопросы