search

KULeuven-DeptCW / AaC-Exc

Excercise sessions of "Automata and Computability" (G0P84A).
http://onderwijsaanbod.kuleuven.be/syllabi/n/G0P84AN.htm
GNU General Public License v3.0
1 stars 3 forks source link

FINITE_CSG #12

Closed KommuSoft closed 9 years ago

KommuSoft commented 9 years ago

Is FINITE_CSG beslisbaar?

KommuSoft commented 9 years ago

Het is niet beslisbaar. Immers zou je anders E_CSG kunnen beslissen:

Je neemt een CSG, en voegt er volgende regel aan toe:

S -> S '0' ('0' is een karakter).

Het gevolg is dat elke string s die in de originele grammatica aanvaard werd, ook aanvaard woord in de nieuwe alsook s0, s00, s000,... Dan zou je de beslisser voor FINITE_CSG kunnen oproepen. Indien de oorspronkelijke taal leeg zou zijn, is de nieuwe dat ook, dus is de taal finite, indien de oude taal minstens een string bevat, "boost" je die en is de taal oneindig. Je zou dus aan de hand van het resultaat van FINITE_CSG, E_CSG kunnen beslissen, maar E_CSG is onbeslisbaar.