Доказательство языка является регулярным

Пусть Σ — конечный алфавит и L ⊆ Σ — язык. Пусть Σ0 ⊆ Σ. Для каждой строки w = w1 · · · wn ∈ Σ определим res(w, Σ0) = y1 · · · yn, где yi = wi, если wi ∈ Σ0, и yi =, если wi ∈ Σ \ Σ0, для каждый 1 ≤ i ≤ n. (Например, res(абракадабра, {a, b}) = abaaaba.) Тогда определим res(L, Σ0) = {res(w, Σ0) : w ∈ L}

У меня есть очень общее направление и мыслительный процесс для этих проблем, однако я не совсем уверен, что смогу построить жизнеспособное доказательство для следующих проблем. Если бы кто-нибудь мог указать мне правильное направление, это было бы очень признательно.

(a) Покажите, что если L ⊆ Σ* ? регулярно и Σ0 ⊆ Σ, res(L, Σ 0 ) должно быть регулярным.

Я знаю, что для этого языка невозможно создать DFA. Так что мне придется выяснить по-другому. Подмножество любого регулярного языка не обязательно является регулярным.

(b) Покажите, что если L ⊆ Σ* контекстно-свободен и Σ0 ⊆ Σ, res(L, Σ0) должен быть контекстно-свободным.

Я знаю, что одним из способов решения этой проблемы было бы предоставление контекстно-независимой грамматики

(c) Покажите, что если L ⊆ Σ* и res(L, Σ 0 ) регулярно, когда Σ0 ⊂ Σ, то L может не быть регулярным.

Относительно этого вопроса мы можем сказать, что даже если L не является регулярным, пустой язык является регулярным подмножеством этого языка. Это верно для всех языков (независимо от того, является ли он обычным или нет)


dfa computation-theory context-free-grammar nfa
person CS959595    schedule 16.03.2016    source источник
comment
Если вам нужна помощь с домашним заданием, по крайней мере, покажите некоторые доказательства того, что вы пытались, и спросите о конкретных подзадачах. Просто вставить четыре задачи и сказать, что у меня есть идея, но, пожалуйста, скажите мне, что ответ вряд ли привлечет какое-либо положительное внимание!   -  person dovetalk    schedule 17.03.2016
comment
Вы действительно имеете в виду, что L является подмножеством алфавита?   -  person John Coleman    schedule 17.03.2016
comment
@JohnColeman да, это то, что на самом деле говорится в задании.   -  person CS959595    schedule 17.03.2016
comment
@ CS959595 Это почти наверняка опечатка, так как в этом мало смысла.   -  person John Coleman    schedule 17.03.2016
comment
@JohnColeman Это то, что я сначала подумал, однако, спросив моего профессора, мне сказали, что это действительно было задумано.   -  person CS959595    schedule 17.03.2016
comment
@ CS959595 Странно - мне нужно еще немного подумать об этом.   -  person John Coleman    schedule 17.03.2016

Ответы (2)


arrow_upward
0
arrow_downward

Я тоже работаю над этим вопросом, вот мои мысли

for a: если L является регулярным, его можно представить регулярным выражением, поэтому должна быть возможность составить регулярное выражение для L'.

для b: создайте CFG, где терминалы, найденные в V и R из {V,E',R,S}, просто включают терминалы E'

для c: предположим, что res(L, E') является регулярным, поэтому, пока алфавит является истинным подмножеством в том смысле, что он не может совпадать с алфавитом L. L не обязательно должен быть регулярным.

Это только мои первоначальные мысли, так что отнеситесь к ним с недоверием (может быть, кто-то еще может дать отзыв)

person Guest    schedule 17.03.2016

arrow_upward
0
arrow_downward

Хотя очевидно, что это домашнее задание, предложение для части (а) состоит в том, чтобы изучить свойства замыкания для обычных языков.

Взгляните на L, предоставленный язык в res(L, Σ’). Теперь взглянем на язык (назовем его L') над алфавитом Σ'.

Теперь давайте посмотрим на ваш пример:

res(abracadabra, {a, b}) = abaaaba

В этом сценарии L ∈ {абракадабра} и L' ∈ {абаааба}

Какую стандартную операцию над множествами мы можем использовать между этими двумя языками, L и L', чтобы создать множество, состоящее только из элементов, общих для каждого языка?

Если вы взглянули на свойства замыкания для обычных языков, я уверен, вы увидите идеальное соответствие!

person Trent    schedule 17.03.2016