Язык L не является контекстно-свободным языком.
Но может ли L* быть контекстно-свободным языком?
Может ли неконтекстно-свободный язык L быть контекстно-свободным при итерации?
comment
Вопросы о Pure-CS лучше задавать на Computer Science.
- person AakashM schedule 16.10.2013
Ответы (1)
Да, это возможно. В качестве примера рассмотрим алфавит = {1} и пусть L будет языком { 1p | p — простое число}. Вы можете доказать, что этот язык не является контекстно-свободным, используя лемму о накачке.
Однако язык L* — это множество всех строк, кроме 1. Причина этого в том, что
- L*, потому что N* для любого языка N.
- 12 L*, потому что 2 — простое число.
- 13 L*, потому что 3 — простое число.
- 1n L* для любого n 2, потому что вы можете начать либо с 12, либо с 13 и соединить соответствующее количество копий 1. 2 к нему.
Этот язык действительно не зависит от контекста, и вы можете доказать это, написав для него грамматику.
Надеюсь это поможет!
person
templatetypedef
schedule
09.10.2013
Спасибо, что неоднократно удивляли меня красивыми математическими истинами :-)
- person ; 10.10.2013
Спасибо! Используя {1р | p — простое число } действительно гениально! Кстати, не могли бы вы уделить время еще одному моему вопросу? stackoverflow.com/q/19282963/2853961
- person ylorn; 10.10.2013
Поправьте меня, если я ошибаюсь, но я думаю, что 1ⁿ ∈ L* для любого n ≥ 2, а не 1ⁿ ∈ L для любого n ≥ 2.
- person ylorn; 10.10.2013
