Is de tekst die u ons aanraadde van Frederik over primitief recursieve functies toegelaten op het examen?

Als ik taal van TM's wil herkennen, dan maak ik een TM aan om die taal te herkennen Maar hoe zit het dan met deze laatste TM, deze wordt toch nog niet meer herkend, of gaat die wel zichzelf herkennen?

Om dit bewijzen:

Is het voldoende om zeggen dat we alle strings die gegeneerd worden door de CFG van de gegeven CFL, geven aan een TM die de overeenkomstige PDA van de CFL simuleert, enzo afleiden of de we de CFL herkennen?

Indien dit niet voldoende zou zijn, moet ik dan eerst een beslisser maken die gebruik maakt van het feit dat A_CFG beslisbaar is?

Hoe kan je makkelijk verifiëren of een gegeven CFL deterministisch is of niet?
De lange weg is:

1. Maak er een PDA van
2. Maak deze PDA nu deterministisch (hoe dit zou gebeuren weet ik ook niet?)

Mijn vraag is dus: kan je dit gemakkelijk op zicht doen bvb voor de taal {a^m b^n c^k |m = n}?

Er staat in dit bewijs dat de accepterende sequentie van toestanden strikt groter is als d.
Waarom moet dit strikt groter zijn en niet groter of gelijk aan?

In de oefening 2.3
De laatste oefening van primitieve recursie wordt de formule voltuit geschreven.
Ik wou de formule over meerder lijnen kunnen uitschrijven maar dat blijk niet te lukken: de volgende dingen heb ik al geprobeerd:

\begin{equation}
\begin{split}
de formule
\end{split}
\end{equation}

en

\usepackage{breqn}

\begin{dmath}
de formule
\end{dmath}

Any solution?

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?

Deelvraag 5 ontbreekt, deelvraag 6 is genummerd als 5.

Bij deze oefening wordt:
0* |1* | 0 (0|1)* 0 |1 (0|1)* 1
als antwoord gegeven.

De strings 10101 of 01010 bevatten beide evenveel de substring 01 en 10:

• 10 10 1 en 1 01 01
• 01 01 0 en 0 10 10
  Maar bovenstaande reguliere expressie kan deze toch niet genereren?

Ik heb gevonden op internet dat dit een triviale eigenschap is.
Komt dit doordat een TM machine met oneven aantal staten steeds kan omgevormd worden naar een TM met een even aantal staten? Hoe gebeurt dit dan?
Als dat zo is dan kunnen we toch gewoon zeggen dat Neg_P leeg is en vandaar de trivialiteit veronderstel ik?

Is FINITE_CSG beslisbaar?

In oefenzitting 7 die we van professor Demoen kregen waren er nog 2 extra oefeningen 7 en 8 voorzien dacht ik?

Is een triviale eigenschap altijd beslisbaar?

Klopt als ik over de machine H_s in st 3.11.2 het volgende zeg:

L(H_s) = {0^n 1^n} als H_s de string s niet accepteert?

In de opgave staat dat er een i en j moet bestaan waarvoor w_i = w_j^R maar als n = 1 klopt dit toch niet? Ook in de oplossing wordt dit niet afgedwogen ofwel?

Als ik een bestend apart wil compileren bvb met texmaker moet ik de lijn
\usepackage[backend=biber]{biblatex}
toevoegen. Bestaat hier geen andere manier voor?