Języki, automaty i obliczenia/Test 14: Języki maszyn Turinga i typu (0). Rozstrzygalność

From Studia Informatyczne

Wskaż zdania prawdziwe:

Automat liniowo ograniczony może dopisywać literę na początku lub na końcu czytanego słowa.

Maszyna Turinga może zmieniać długość czytanego słowa.

Automat ze stosem może w jednym przejściu dowolną literę słowa zapisanego na stosie zastąpić dowolnym słowem nad alfabetem stosu.

Automat ze stosem i automat liniowo ograniczony mogą zmieniać stan bez czytania litery.

Automat liniowo ograniczony może w czytanym słowie zmieniać dowolną literę z alfabetu taśmy


Wskaż zdania prawdziwe:

Każda gramatyka bezkontekstowa jest kontekstowa.

Język \displaystyle L jest akceptowany przez deterministyczny automat ze stosem wtw gdy jest akceptowany przez niedeterministyczny automat ze stosem.

Każda gramatyka regularna jest bezkontekstowa.

Każdy język bezkontekstowy jest kontekstowy.

Język \displaystyle L jest akceptowany przez deterministyczny automat skończenie stanowy wtw gdy jest akceptowany przez niedeterministyczny automat skończenie stanowy.


Rodziny \displaystyle \mathcal{L}_0 i \displaystyle \mathcal{L}_1 mają następujące własności:

są zamknięte na sumę

są zamknięte na uzupełnienie

są zamknięte na katenację

są zamknięte na iloczyn mnogościowy

są równe


Wskaż zdania prawdziwe:

każda gramatyka kontekstowa jest rozszerzająca

każda gramatyka bezkontekstowa jest rozszerzająca

każda gramatyka regularna jest rozszerzająca

dla każdej gramatyki rozszerzającej istnieje równoważna jej gramatyka kontekstowa

dla każdej gramatyki bezkontekstowej istnieje równoważna jej gramatyka rozszerzająca


Wskaż zdania prawdziwe:

Istnieje gramatyka rozszerzająca, dla której nie istnieje równoważna jej gramatyka kontekstowa.

Dla dowolnej gramatyki kontekstowej z markerem końca istnieje równoważna jej gramatyka kontekstowa.

Dla dowolnego języka kontekstowego \displaystyle L istnieje automat liniowo ograniczony \displaystyle \mathcal{A}_{LO} taki, że \displaystyle L=L(\mathcal{A}_{LO}).

Iloczyn mnogościowy dwóch języków kontekstowych jest językiem bezkontekstowym.

Dla dowolnego języka \displaystyle L rozpoznawanego przez automat liniowo ograniczony istnieje gramatyka \displaystyle G taka, że \displaystyle L=L(G).


Wskaż klasy języków domknięte ze względu na iloczyn mnogościowy:

\displaystyle \mathcal{L}_0

\displaystyle \mathcal{L}_3

\displaystyle \mathcal{L}_2

\displaystyle \mathcal{L}_1

rodzina języków akceptowanych przez automaty skończenie stanowe


Klasa \displaystyle \mathcal{L}_0 nie jest zamknięta ze względu na:

sumę

uzupełnienie

katenację

gwiazdkę Kleene'ego

przecięcie


Rozważmy język:

\displaystyle  L=\{a^n b^n c^n\: n\geq 5\}

Które z poniższych twierdzeń są prawdziwe:

problem, czy dane \displaystyle w\in A^* spełnia \displaystyle w\in L jest nierozstrzygalny

\displaystyle L\in \textbf{PSPACE}

\displaystyle L\in \textbf{NP}

maszyna Turinga rozpoznająca język \displaystyle L musi być niedeterministyczna lub posiadać \displaystyle 5 taśm

\displaystyle L\in \textbf{P}


Gramatyki typu (0) generują klasę języków:

rekurencyjnych, ale tylko przy założeniu tezy Churcha

zawierającą klasę języków rekurencyjnie przeliczalnych, a przy dodatkowym założeniu tezy Churcha, także klasę języków rekurencyjnych

identyczną z klasą języków rozpoznawalnych przez automat liniowo ograniczony

przy założeniu tezy Churcha, identyczną z klasą języków rozpoznawanych przez deterministyczną maszynę Turinga

zawierającą wszystkie języki które są rozpoznawane przez deterministyczną maszynę Turinga, ale istotnie węższą niż klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga.


Załóżmy, że \displaystyle L_1 \propto L_2 oraz dodatkowo \displaystyle L_1 \in \textbf{NP}. W tej sytuacji:

wprost z definicji transformacji \displaystyle \propto wynika, że \displaystyle L_2 \in NP

\displaystyle L_1 \in PSPACE

jeśli dodatkowo \displaystyle L_1 \not\in \textbf{P} to \displaystyle L_2 \not\in \textbf{P}

jeśli język \displaystyle L_1 jest \displaystyle \textbf{P}-zupełny, to \displaystyle L_2 jest \displaystyle \textbf{P}-trudny

wykluczony jest warunek \displaystyle L_2 \in \textbf{PSPACE}


Które z poniżej wymienionych problemów są nierozstrzygalne:

problem niejednoznaczności dla gramatyk bezkontekstowych

problem, czy \displaystyle L_1\cap L_2\neq \emptyset dla języków regularnych

problem, czy dana gramatyka typu (0) generuje język pusty

problem Posta nad alfabetem \displaystyle A=\{1,2,\dots,n\} gdzie \displaystyle n\geq 1.

problem, czy \displaystyle L_1 \subset L_2 dla języków zadanych przez gramatyki kontekstowe


Które z poniższych maszyn są równoważne maszynie Turinga?

maszyna Turinga z wieloma taśmami

maszyna Turinga z wieloma głowicami

maszyna Turinga z taśmą jednostronnie nieskończoną

maszyna Turinga z wieloma taśmami, z których każda jest obustronnie ograniczona

maszyna Turinga niedeterministyczna


Stwierdzenie mówiące, iż każda efektywna procedura (algorytm) da się opisać przez pewną maszynę Turinga, znane jest jako:

twierdzenie Kleene'ego

twierdzenie Nerode'a

teza Churcha

twierdzenie Savitcha

problem P = NP