Индукция по струне? (Автоматы, связанные с)

Question

Честно говоря, все, что я знаю о математической индукции следующим образом:

1. prove P(0) - base step 
2. for all n ≥ 1, prove (P(n − 1) -> P(n)) - inductive step 

And here is image of my induction problem that I am struggling now (please click)

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

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

Большого спасибо, если вы можете мне помочь выше проблем с тщательным объяснением ..

Answer 1

Как намек, пусть Р (к) утверждением «любой язык с ровно к строкам является регулярным.» Используя вашу идею индукции, вам нужно будет сделать следующее:

1. Докажите, что любой язык с 0 строками в нем является регулярным. Что вы можете сказать о языке, в котором нет строк? Можете ли вы создать DFA, NFA или regex для такого языка?

2. Предположим, что любой язык с n-1 строками является регулярным, а затем докажите, что любой язык с n строками является регулярным. Если в нем есть n строк, вы можете разбить его на язык с n-1 строками в нем и язык с одной строкой в ​​нем. Что вы можете сказать о первом языке? Если у вас есть регулярное выражение для него, что вы можете сделать, чтобы адаптировать его к регулярному выражению для языка с еще одной строкой?