Lab Session #9 #
Agenda #
- Non-determinism:
- PDA
- TM
Non-deterministic Pushdown Automaton (NDADA) #
Definition: NDPDA #
A NDPDA is a tuple \(<Q,I,Γ,δ,q0,Z0,F>\) , where \(Q,I,Γ,δ,q0,Z0,F\) are defined as in (D)PDA and the transition function is defined as
\(δ:Q×(I∪{eps})×Γ→P_F(Q×Γ^∗)\)where \(P_F\) indicates finite subsets.
Exercices #
Build NDPDAs that recognise the following languages:
- \(L1=\{ww^R|w∈{a,b}^+\}\) where \(w^R\) is the reversed string \(w\) .
- \(L2=\{a^{n}b^{n}|n≥1\}∪\{a^{n}b^{2n}|n≥1\}\) .
- \( L3=\{a^{i}b^{j}c^{k}d^{l}|(i=k\) or \(j=l),i≥1,j≥1\} \) .
Non-deterministic Turing Machine (NDTM) #
To define a NDTM, we need to change the transition function (all the other elements reamin as in a (D)TM):
Definition: NDTM #
A NDTM is a tuple \(<Q,I,Γ,δ,q0,Z0,F>\) , where \(Q,I,Γ,δ,q0,Z0,F\) are defined as in (D)TM and the transition function is defined as
\(δ:(Q−F)×(I∪\{\_\})×(Γ∪\{\_\})^k→P(Q×(Γ∪\{\_\})^k×\{R,L,S\}^{k+1}) \)Acceptance: Among the various possible runs (with the same input) of the NDTM, it is sufficient that one of the run (instances) reaches the final state. The input string may not be fully consumed to be considered as ‘accepted’.
Exercices #
Build NDTMs that recognise the following languages:
- \(L1=\{ww|w∈\{a,b\}^+\}\) .
- \(L2=\{ww^R|w∈\{a,b\}^+\}\) , where \(w^R\) is the reversed string \(w\) .