Lab Session #9
# Agenda
# PDA TM Non-deterministic Pushdown Automaton (NDADA)
# Definition: NDPDA
# A NDPDA is a tuple
< Q , I , Γ , δ , q 0 , Z 0 , F > <Q,I,Γ,δ,q0,Z0,F> < Q , I , Γ , δ , q 0 , Z 0 , F >
, where Q , I , Γ , δ , q 0 , Z 0 , F Q,I,Γ,δ,q0,Z0,F Q , I , Γ , δ , q 0 , Z 0 , F
δ : Q × ( I ∪ e p s ) × Γ → P F ( Q × Γ ∗ ) δ:Q×(I∪{eps})×Γ→P_F(Q×Γ^∗) δ : Q × ( I ∪ e p s ) × Γ → P F ( Q × Γ ∗ ) where P F P_F P F
Exercices
# Build NDPDAs that recognise the following languages:
L 1 = { w w R ∣ w ∈ a , b + } L1=\{ww^R|w∈{a,b}^+\} L 1 = { w w R ∣ w ∈ a , b + } w R w^R w R w w w L 2 = { a n b n ∣ n ≥ 1 } ∪ { a n b 2 n ∣ n ≥ 1 } L2=\{a^{n}b^{n}|n≥1\}∪\{a^{n}b^{2n}|n≥1\} L 2 = { a n b n ∣ n ≥ 1 } ∪ { a n b 2 n ∣ n ≥ 1 } L 3 = { a i b j c k d l ∣ ( i = k L3=\{a^{i}b^{j}c^{k}d^{l}|(i=k L 3 = { a i b j c k d l ∣ ( i = k or j = l ) , i ≥ 1 , j ≥ 1 } j=l),i≥1,j≥1\} j = l ) , i ≥ 1 , j ≥ 1 } Solutions
▾
(1)
# L 1 = { w w R ∣ w ∈ a , b + } L1=\{ww^R|w∈{a,b}^+\} L 1 = { w w R ∣ w ∈ a , b + }
where
w R w^R w R
is the reversed string
w w w
.
NDPDA that recognises this language:
(2)
# L 2 = { a n b n ∣ n ≥ 1 } ∪ { a n b 2 n ∣ n ≥ 1 } L2=\{a^{n}b^{n}|n≥1\}∪\{a^{n}b^{2n}|n≥1\} L 2 = { a n b n ∣ n ≥ 1 } ∪ { a n b 2 n ∣ n ≥ 1 }
.
PDA that recognises this language:
Another valid PDA that recognises this language:
NDPDA that recognises this language:
(3)
# L 3 = { a i b j c k d l ∣ ( i = k L3=\{a^{i}b^{j}c^{k}d^{l}|(i=k L 3 = { a i b j c k d l ∣ ( i = k
**or**
j = l ) , i ≥ 1 , j ≥ 1 } j=l),i≥1,j≥1\} j = l ) , i ≥ 1 , j ≥ 1 }
.
NDPDA that recognises this language:
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 , Γ , δ , q 0 , Z 0 , F > <Q,I,Γ,δ,q0,Z0,F> < Q , I , Γ , δ , q 0 , Z 0 , F > Q , I , Γ , δ , q 0 , Z 0 , F Q,I,Γ,δ,q0,Z0,F Q , I , Γ , δ , q 0 , Z 0 , F
δ : ( Q − F ) × ( I ∪ { _ } ) × ( Γ ∪ { _ } ) k → P ( Q × ( Γ ∪ { _ } ) k × { R , L , S } k + 1 ) δ:(Q−F)×(I∪\{\_\})×(Γ∪\{\_\})^k→P(Q×(Γ∪\{\_\})^k×\{R,L,S\}^{k+1}) δ : ( 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:
L 1 = { w w ∣ w ∈ { a , b } + } L1=\{ww|w∈\{a,b\}^+\} L 1 = { w w ∣ w ∈ { a , b } + } L 2 = { w w R ∣ w ∈ { a , b } + } L2=\{ww^R|w∈\{a,b\}^+\} L 2 = { w w R ∣ w ∈ { a , b } + } w R w^R w R w w w Solutions
▾
(1)
# L 1 = { w w ∣ w ∈ { a , b } + } L1=\{ww|w∈\{a,b\}^+\} L 1 = { w w ∣ w ∈ { a , b } + }
.
NDTM that recognises this language:
(2)
# L 2 = { w w R ∣ w ∈ { a , b } + } L2=\{ww^R|w∈\{a,b\}^+\} L 2 = { w w R ∣ w ∈ { a , b } + }
, where
w R w^R w R
is the reversed string
w w w
.
NDTM that recognises this language:
