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

Voorbeeld taal-invariante eigenschap #19

Open warreee opened 9 years ago

warreee commented 9 years ago

Wanneer Rice niet mag gebruikt worden vind ik enkel voorbeelden van nt-triviale eigenschappen. Ik kan me geen talen bedenken die niet voldoen aan de taal-invariante eigenschap.

Kent u een voorbeeld?

ingdas commented 9 years ago

De taal bestaat uit strings -> Taal-invariant maar triviale eigenschap -> Geen Rice De turingmachine bestaat uit exact 5 toestanden -> Niet-taalinvariant -> Geen Rice Er bestaat geen turingmachine met minder dan 5 toestanden die dezelfde taal beschrijft -> Taal-invariant & niet triviaal -> Rice