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

Я должен доказать, что это утверждение ложно. Если L1 = {аб| a∈L2, b∉L2} — регулярный язык, то L2 — регулярный язык.

(a и b — строки.) (Предположим, что L1 и L2 имеют одинаковые алфавиты.)

Моя работа:
Вопрос можно переписать так: если L2 правильный, то L1 нерегулярный. (Докажите, что это правда)

доказательство от противного: если L2 регулярно, то L1={ab| a∈L2, b∉L2} не является регулярным

Я не уверен, что делать после этой строки. Это правильный подход? Может ли кто-нибудь дать мне несколько советов о том, как это сделать?


regular-language
person Jonathan Lam    schedule 27.11.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Пусть A = «L1 = {ab| a∈L2, b∉L2} — регулярный язык».
Пусть B = «L2 — регулярный язык».

Задача состоит в том, чтобы доказать, что A B ложно. Это эквивалентно доказательству A B. Что на английском языке гласит:

L1 = {аб| a∈L2, b∉L2} — регулярный язык, но L2 — нерегулярный язык.

Таким образом, одна из тактик может состоять в том, чтобы найти нерегулярный L2, который приведет к тому, что L1 будет регулярным. Если вы можете это сделать, то у вас есть контрпример, и вы доказали, что исходное утверждение ложно.

person John Kugelman    schedule 27.11.2012