Fondamentisti anonimi
Fondamentisti Anonimi Quiz
Metti alla prova le tue conoscenze sulla teoria dei linguaggi formali attraverso il nostro quiz interattivo "Fondamentisti Anonimi". Con domande che spaziano dalle espressioni regolari agli automi, questo quiz è ideale per chi desidera approfondire la propria comprensione della materia in modo divertente.
• Testa le tue competenze teoriche
• Sfida te stesso con domande a scelta multipla
• Apprendi nuovi concetti e applica le tue conoscenze
1. L’espressione regolare ∅a* + ∅*denota il linguaggio:
(a) Nessuna delle altre
(b) {ε}
(c) {a}*
(d) {ε, a}
(e) ∅
2. Quale delle seguenti identita tra E.R. non è valida
(a) nessuna
(b) (ε + r*r) = r*
(c) (r* + s*)* = (r*s*)*
(d) ε* = ∅*
(e) (rs)*r = r(sr)*
3. Quanti stati ha il DFA minimo che accetta il linguaggio su alfabeto {a, b, c} denotato dall’E.R. ((a+b)(a+b)...(a+b))* (a+b) ripetuto n volte
(a) n+2
(b) nessuna
(c) n+1
(d) n
(e) 2*n
4. Qual `e la cardinalità dell’insieme delle MdT con n stati e m simboli
(a) (2*n*m+1)2n
(b) m^n
(c) |P(n)|
(d) nessuna
(e) |m|
5. Un sottoinsieme di un linguaggio acontestuale
(a) `e decidibile
(b) nessuna
(c) `e monotono
(d) `e regolare
(e) `e acontestuale
6. Quali delle seguenti coppie hanno diverso peso espressivo
(a) DFA e NFA
(b) MdT ordinate e MdT con pi`u nastri
(c) APD e APND
(d) nessuna
(e) ER ordinarie ed ER senza ε
7. Quale delle seguenti identit`a tra espressioni regolari NON `e valida
(a) (r*+s*)*=(r*s*)
(b) (rs+r)*rs=(rr*s)*
(c) (ε+r*r)=r*
(d) (rs)*r=r(sr)*
(e) ε* = ∅*
8. Quale `e la cardinalit`a dell’insieme dei linguaggi acontestuali su di un alfabeto di n > 0 simboli
(a) nessuna delle altre
(b) |P(N)|
(c) |N|
(d) 2^(2n)
(e) 2^n
9. Il complemento di un linguaggio finito
(a) `e acontestuale non regolare
(b) `e irregolare
(c) `e finito
(d) `e regolare
(e) nessuna delle altre
10. Quale delle seguenti identit`a tra espressioni regolari non `e valida
(a) (ε*+ ∅)*= ∅*
(b) (rs)*r=r(sr)*
(c) r*r*=rr*+ε*
(d) (s*r)*s*=(r*s)*r*
(e) s(rs+s)*r=rr*s(rr*s)*
11. Si considerino le seguenti grammatiche espresse in forma concisa e si dica quale di queste `e ambigua o se nessuna lo `e
(a) S -> SS|a
(b) S -> aS|a
(c) nessuna
(d) S -> SaS|ε
(e) S -> aSa|ε
13. Gli insiemi ricorsivamente enumerabili non sono chiusi rispetto a:
(a) rimozione di un elemento
(b) unione
(c) intersezione
(d) nessuna delle altre
(e) differenza
14. Quale delle seguenti espressioni regolari Ε={a, b, c} denota il linguaggio {ε}U {w 2 ⌃*| il numero di occorrenze di a in w `e pari e positivo}
(a) ((b+c)*a(b+c)*a)*
(b) ((b*+c*)a(b*+c*)a(b*+c*))*
(c) ((b*c*)a(b*c*)a(b*c*))*
(d) (a(b+c)*a(b+c)*)*
(e) ((b+c)*a(b+c)*a(b+c)*)*
15. Si considerino le espressioni regolari sull’alfabeto Ε={0,1} r1=(0+1)*(0011+1010)(0+1)* r2=ε+(0+10+110)*(ε+1+11)
(a) [|r1|] ⊃ [|r2|]
(b) nessuna
(c) [|r1|]=[|r2|]
(d) [|r1|] ∩ [|r2|] =∅
(e) [|r1|] ⊂ [|r2|]
16. Un sottoinsieme di un linguaggio regolare `e
(a) monotono
(b) c.f.
(c) Regolare
(d) decidibile
(e) nessuna
17. Quali dei seguenti automi pu`o accettare {x ∈ {0, 1}*| n0(x) = n1(x)} con nb(ε)=0 e nb(aw)=1-|a-b|+nb(w)?
A) ε-NFA
B) NFA
(c) nessuna delle altre
(d) APND
E) DFA
18. L’affermazione ”Se I ⊆ N `e un insieme X e I’ = N \ I allora anche I’ `e X” se al posto di X scrivo
(a) ’ricorsivamente enumerabile’
(b) ’ricorsivo’
(c) ’non ricorsivamente enumerabile’
(d) nessuna delle altre
(e) ’ricorsivamente enumerabile non ricorsivo’
19. Quante sono le sottostringhe di una stringa di lunghezza n su di un alfabeto m > 0 simboli?
(a) n(n + 1) \ 2
(b) 1 + n(n + 1) \ 2
(c) m*n
(d) m(m + 1) \ 2
(e) 1 + m(n + 1) \ 2
20. Scriviamo dfa(x) e apnd(y) a significare che x `e un DFA e y un APND; scriviamo x ⌘ y per dire che x e y sono equivalenti. Quale delle seguenti formule logiche rappresenta il fatto che, dato comunque UN DFA, esiste un APND equivalente?
(a) ∀x : ∃y.(df a(x) ^ apnd(y) ^ x ≡ y)
(b) ¬∀y : (∃x.df a(x) ) (∃y.apnd(y) ^ x ≡ y))
(c) nessuna delle altre
(d) ∀x : df a(x) ) (∃y.apnd(y) ^ x ≡ y))
(e) ∀x : ∃y.(df a(y) ^ apdn(x) ^ x ≡ y))
21. Identificare le eventuali affermazione vere tra le seguenti, che riguardano l’uso delle MdT come riconoscitori di linguaggi formali
(a) più di una delle altre
(b) una MdT `e pi`u potente di un ε-NFA perch´e il controllo della MdT non `e a stati finiti
(c) un ε-NFA++ che potesse riavvolgere il nastro (di input) sarebbe tanto potente quanto una MdT
(d) una MdT che muove la testina solo a destra `e tanto potente quanto un ε-NFA
(e) nessuna delle altre
22. Quale `e la cardinalit`a dell’insieme delle stringhe lunghe n sull’alfabeto Ε?
(a) |P(N)|
(b) n^|Ε|
(c) 2^n
(d) |E|^n
(e) |N|
23. Quale dei seguenti linguaggi sull’alfabeto E={0,1,2} `e regolare?
A) {0^n ∈ E*|n≥1 è primo}
(b) nessuna delle altre
(c) {0^n1^m2^(n+m) ∈ E*|n≥1, m≥1}
D) {0^n1^m1^(n+m) ∈ E*|n≥1, m≥1}
(e) {0^(2n+1)∈ E*|n≥1, m≥1}
24. Quale delle seguenti espressioni regolari sull’alfabeto E={0,1} rappresenta il linguaggio delle stringhe che contengono un numero ’0’ divisibili per 3?
(a) nessuna delle altre
(b) (1*01*01*0)*+1*
(c) ((0+1)*0(0+1)*0(0+1)*0(0+1)*)*+1*
(d) (1*01*01*01*)*
(e) (1*01*01*01*)*+1*
25. Qual `e la cardinalit`a delle funzioni totali
(a) |{0, 1} -> N|
(b) |N ->{0}|
(c) nessuna delle altre
(d) |N|
(e) |p(N)|
26. Si dica quanti stati ha un DFA minimo che accetta il linguaggio sull’alfabeto {a, b, c} denotato dall’E.R. ε + (a+b)(a+b)...(a+b) n volte
(a) n+2
(b) nessuna delle altre
(c) 2n
(d) n
(e) n+1
27. Si consideri l’automa a pila M =< {q}, {a, b}, {a, b, s}, ∂,q,S,∅> dove ∂(q,ε,S)={(q,bSa),(q,bS),(q,SS),(q,ε)}
∂(q,a,a)= {(q,ε)}
∂(q,b,b)= {(q,ε)}
Si dica quale delle seguenti stringhe non è accettata per pila vuota
(a) ε
(b) babb
(c) baa
(d) tutte le altre sono accettate
(e) bbaa
28. Quale delle seguenti espressioni regolari su E={a, b, c} denota il linguaggio {w ∈ {a, b, c}*| il numero di occorrenze di a in w `e dispari }?
(a) ((b+c)*a(b+c)*)((b+c)*a(b+c)*a)*
(b) ((b+c)*a(b+c)*a(b+c)*)*(a(b+c)*)
(c) ((b+c)*a(b+c)*a)*((b+c)*a(b+c)*)
(d) ((b+c)*a)((b+c)*a(b+c)*a(b+c)*)*
(e) (a(b+c)*)((b+c)*a(b+c)*a(b+c)*)*
29. Quale dei seguenti automi si arresta sempre dopo aver e↵ettuato un numero finito di transizioni se riceve in input una sequenza finita di simboli (non blank per la MdT)?
(a) APND
(b) DFA
(c) MdT
(d) APD
(e) Nessuna delle altre
30. Quali dei seguenti linguaggi sull’alfabeto E={a, b} sono regolari?
(a) {a^na^((n+1)^(2-n^2) ∈E*|n≥0}
(b) {x ∈ E*| ha tante a quante b }
(c) {x ∈ E*| x ha pi`u a che b }
(d) {a^nb^n ∈ E*|n ≥1}
(e) Nessuna delle altre
31. Qual `e la cardinalit`a degli insiemi non acontestuali?
(a) |{0, 1} -> N|
(b) |N -> {0}|
(c) nessuna delle altre
(d) |N|
(e) |p(N)|
32. Quali fra I seguenti problemi sono decidibili
1. Se l’intersezione di due linguaggi regolari `e infinita
2. Se una data grammatica `e ambigua
3. Se due APND accettano lo stesso linguaggio
4. Se una grammatica `e acontestuale
(a) 2e4
(b) nessuna delle altre
(c) 2e3
(d) 1e2
(e) 1e4
33. Quali delle seguenti espressioni regolari `e tale che il linguaggio denotato non contiene stringhe con due 1 consecutivi?
(a) pi`u di una delle altre
(b) (0+1)*(0+ε)
(c) (01+10)*
(d) (1+ε)(01+0)*
(e) nessuna delle altre
34. Il complemento di un linguaggio acontestuale
(a) `e decidibile
(b) `e regolare
(c) `e finito
(d) `e acontestuale
(e) nessuna delle altre
35. La chiusura di Kleene di un linguaggio acontestuale
(a) `e infinita
(b) `e acontestuale
(c) `e monotona non acontestuale
(d) `e regolare
(e) nessuna delle altre
36. Siano E un alfabeto e P, Q, R ⊆ E* Allora (P ∩ Q ∩ R) U (P¯ ∩ Q ∩ R) U Q¯ U R¯ `e uguale a
(a) nessuna delle altre
(b) P¯ U Q¯ U R¯
(c) P U Q¯ U R¯
(d) E*
(e) Q¯ U R
37. Quale delle seguenti identit`a tra espressioni regolari non `e valida
(a) nessuna delle altre
(b) ε*=∅*
(c) (rs)*r=r(sr)*
(d) r*r=rr*+ε
(e) (r+s)*=(r*s)*r*
38. Si consideri un APND a uno stato q, con alfabeto dello stack {a, b, s},
simbolo iniziale dello stack S e la funzione di transizione definita da
∂(q,ε,S)= {(q,sb),(q,asb),(q,abb)}
∂(q,a,a)= {(q,ε)}
∂(q,b,b)= {(q,ε)}
Si dica quale linguaggio viene generato da tale automa per pila vuota
simbolo iniziale dello stack S e la funzione di transizione definita da
∂(q,ε,S)= {(q,sb),(q,asb),(q,abb)}
∂(q,a,a)= {(q,ε)}
∂(q,b,b)= {(q,ε)}
Si dica quale linguaggio viene generato da tale automa per pila vuota
A) {a^nb^m|0
(b) nessuno degli altri
C) {a^nb^m|0≤ n
(d) {a^nb^m|0 ≤ n ≤ m}
(e) {a^nb^m|0 < n ≤ m}
39. Se F `e un linguaggio finito e L/F `e regolare, allora:
(a) L `e finito
(b) L `e regolare
(c) L `e infinito
(d) L=F
(e) nessuna delle altre
40. La chiusura di Kleene di un linguaggio monotono
(a) `e regolare
(b) `e acontestuale
(c) nessuna delle altre
(d) `e infinita
(e) `e monotona non acontestuale
41. Qual è la cardinalità dell'insieme degli APND con stati Q ed alfabeti E ed R?
(a) |Q||R| * 2^(|Q|^2*|E|+|Q|^2+n)
(b) |Q||R| * 2^(|Q||R||E|+|Q|+|E|)
(c) |Q||R| * 2^((|Q|+|R|)|Q||R|(|E|+1)+1)
(d) |N|
(e) nessuna delle altre
42. Sia R ⊆ N^2 dato da
R = {(n, m)| |n - m| è 0 o termina con 00 o con 50}.
R è una relazione di
R = {(n, m)| |n - m| è 0 o termina con 00 o con 50}.
R è una relazione di
(a) pi`u di una delle altre
B) equivalenza
(c) nessuna delle altre
(d) ordinamento parziale non totale
(e) ordinamento totale
43. Si dica quanti stati ha un DFA minimo che accetta il linguaggio sull’alfabeto {a, b} denotato dall’espressione regolare ε + (a + b)^n con n ∈ N
(a) n+1
(b) 2n
(c) nessuna delle altre
(d) 2^n
(e) n+2
44. Qual `e la cardinalit`a dell’insieme dei linguaggi non monotoni che si possono definire su di un alfabeto di n > 0 simboli?
(a) 2^(2^n)
(b) |p(N)|
(c) nessuna delle altre
(d) 2^n
(e) |N|
45. Qual `e la cardinalit`a delle funzioni parziali ricorsive?
(a) nessuna delle altre
(b) |N -> {0, 1}|
(c) |N|
(d) |p(N)|
(e) |N -> N|
46. Il complemento di un linguaggio regolare
(a) `e regolare
(b) `e irregolare
(c) `e finito
(d) nessuna delle altre
(e) `e acontestuale non regolare
47. Gli insiemi ricorsivamente enumerabili non sono chiusi rispetto a:
(a) rimozione di un elemento
(b) unione
(c) intersezione
(d) nessuna delle altre
(e) differenza
48. Quali delle seguenti coppie hanno diverso potere espressivo?
(a) DFA e NFA
(b) MdT ordinarie e MdT con pi`u nastri
(c) APD e APND
(d) nessuna delle altre
(e) ER ordinarie ed ER senza ε
49. Si dica quanti stati ha un DFA minimo che accetta il linguaggio sull’alfabeto {a, b, c} denotato dall’espressione regolare ε + (a + b)^n con n ∈ N
(a) n+2
(b) nessuna delle altre
(c) 2n
(d) n
(e) n+1
50. Se C[L2L0,L1] è un compilatore da L0 a L1 scritto in L2 e scriviamo Lx < Ly a significare "Lx è più semplice di Ly" allora
(a) L1
(b)L0
(c)L0<L1
(d) Nessuna delle altre
L1
52. Qual `e la cardinalit`a delle funzioni parziali?
(a) |p(N)|
(b) |{0, 1} -> N|
(c) nessuna delle altre
(d) |N|
(e) |N -> {0}|
51. Quale combinazione delle variabili intere x, y e z fa che la seguente espressione C++ valga 4? (x>y) ? ((x>z) ? x : z) : ((y>z) ? y : z)
(a) x=3, y=4, z=2
(b) x=5, y=5, z=4
(c) x=4, y=5, z=5
(d) nessuna delle altre
(e) x=5, y=4, z=5
53. Si consideri la pi`u semplice grammatica libera contenente le produzioni S -> Sb, s -> aSb, S -> abb. Si dica quale linguaggio viene generato da tale grammatica.
(a) {a^nb^m|0 ≤ n ≤ m}
(b) {a^nb^m|0 < n ≤ m}
(c) nessuna delle altre
(d) {a^nb^m|0 ≤ n
(e) {a^nb^m|0 <n<m}
54. Qual `e la cardinalit`a dell’insieme dei linguaggi non acontestuali su di un alfabeto di n > 0 simboli?
(a) |p(N)|
(b) nessuna delle altre
(c) |N|
(d) 2^n
(e) 2^(2^n)
55. Quali dei seguenti automi pu`o accettare {x ∈ {0, 1}*|x = r(x)} con r(ε) e r(aw) = r(w) * a ?
(a) DFA
(b) APD
(c) ε-NFA
(d) nessuna delle altre
(e) APND
56. Quale delle seguenti espressioni regolari non denota il linguaggio L su E={0, 1} delle stringhe in cui ogni occorrenza di 00 precede tutte le occorrenze di 11?
(a) (10 + 0)*(1 + ε)(01 + 1)*0
(b) (10 + 0)*(1 + 10)*
(c) (10 + 0)*(1 + ε)(01 + 1)*(0 + ε)
(d) due delle altre non denotano L
(e) nessuna delle altre denota L
57. Qual `e la cardinalit`a dell’insieme degli APND con stati Q e alfabeti E ed R?
(a) |Q||R| * 2^(|Q|^2*|E|+|Q|^2+n)
(b) |Q||R| * 2^(|Q||R||E|+|Q|+|E|)
(c) |Q||R| * 2^((|Q|+|R|)|Q||R|(|E|+1)+1)
(d) |N|
(e) nessuna delle altre
58. Se C = C[L L,L} è un compilatore da L a L scritto in L;
I = I[L L] è un interprete per L scritto in L;
P = P ^L è un programma scritto in L;
allora una delle seguenti asserzioni `e falsa:
I = I[L L] è un interprete per L scritto in L;
P = P ^L è un programma scritto in L;
allora una delle seguenti asserzioni `e falsa:
(a) λD.[I](P,D)=[P]
(b) [[C](P)]=[[[C](C)](P)]
(c) λD.[C](P,D)=[P]
(d) λD.[[C](I)](P,D)=[P]
(e)[P]= [[C](P)]
59. La differenza insiemistica di due linguaggi regolari
(a) nessuna delle altre
(b) `e acontestuale non regolare
(c) `e finita
(d) `e regolare
(e) `e monotona non acontestuale
60. Sia r un espressione regolare, rr* si pu`o anche scrivere
(a) r-
(b) r
(c) r+
(d) nessuna delle altre)
(e) r+Ur-
61. Se L `e ricorsivamente enumerabile e L¯ non lo `e, allora L `e:
(a) ricorsivo
(b) finito
(c) pi`u di una delle altre
(d) non ricorsivo
(e) nessuna delle altre
62. Sia G una grammatica in forma normale di Greibach e x ∈ L(G) tale che |x| = n. Quanto `e lunga una derivazione di x in G?
(a) nessuna delle altre
(b) 2n-1
(c) 2n+1
(d) n
(e) 2n
63. Qual `e la cardinalità dell’insieme degli ε-NFA con stati Q e alfabeti E?
(a) |Q| * 2^(|Q||⌃|+|Q|+|E|)
(b) |N|
(c) nessuna delle altre
(d) |Q| * 2^(|Q|^2*|E|+|Q|^2+1)
(e) |Q| * 2^(|Q|(|Q||E|+1))
64. Se L1 e L2 sono linguaggi tali che L2, L1L2 e L2L1 sono regolari, allora:
(a) L1 `e acontestuale
(b) L1 `e monotono
(c) nessuna delle altre
(d) L1 `e finito
(e) L1 `e regolare
65. Qual `e il massimo numero di stati finali per un DFA ottenuto dalla conversione Robin-Scott di un NFA con 7 stati?
(a) 7
(b) 128
(c) 8
(d) nessuna delle altre
(e) 127
67. La somma del minimo e del massimo numero di stati finali per un DFA con n stati `e:
(a) n+2
(b) n
(c) n+1
(d) nessuna delle altre
(e) n-1
68. I linguaggi acontestuali infiniti sono chiusi rispetto a
(a) intersezione
(b) stella di Kleene
(c) differenza insiemistica
(d) complementazione
(e) nessuna delle altre
70. Il complemento di un linguaggio infinito
(a) `e regolare
(b) nessuna delle altre
(c) `e finito
(d) `e infinito
(e) `e decidibile
71. Qual `e il minimo numero di stati per un DFA sull’alfabeto {0, 1} che accetta le stringhe che iniziano e terminano con lo stesso simbolo?
(a) 4
(b) 3
(c) 6
(d) 5
(e) nessuna delle altre
72. Quale dei seguenti automi può dar luogo a sequenze infinite di transizioni?
(a) DFA
(b) NFA
(c) ε-NFA
(d) nessuna delle altre
(e) APND
73. Un linguaggio monotono
(A) `e di tipo 0;
(B) `e di tipo 00
(C) `e di tipo 1;
(D) n´e (A) n´e (B) n´e (C).
74. Qual `e la cardinalit dell’insieme dei linguaggi finiti che si possono definire su di un alfabeto Σ di n > 0 simboli?
(A) 2n;
(B) 2^(2^ n)
(C) |N|;
(D) |℘(N)|
(E) n´e (A) n´e (B) n´e (C) n´e (D)
75. I linguaggi finiti sono chiusi rispetto a
(A) complementazione
B) concatenazione
(C) intersezione;
(D) stella di Kleene
(E) unione;
(F) nessuna di queste
76. L’affermazione “Se I `e un insieme X e I 0 ⊆ I allora anche I' è X”
A) `e vera, se al posto di X scrivo “ricorsivo”;
(B) `e vera, se al posto di X scrivo “ricorsivamente enumerabile”;
(C) `e vera, se al posto di X scrivo “non ricorsivamente enumerabile”
(D) n´e (A) n´e (B) n´e (C)
77. Vero o falso?
(A) ogni funzione totale `e primitiva ricorsiva
(B) ogni funzione primitiva ricorsiva `e totale
(C) ogni funzione totale `e parziale ricorsiva
(D) ogni funzione parziale ricorsiva `e totale
E) ogni funzione parziale `e parziale ricorsiva
(F) n´e (A) n´e (B) n´e (C) n´e (D) n´e (E).
{"name":"Fondamentisti anonimi", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Metti alla prova le tue conoscenze sulla teoria dei linguaggi formali attraverso il nostro quiz interattivo \"Fondamentisti Anonimi\". Con domande che spaziano dalle espressioni regolari agli automi, questo quiz è ideale per chi desidera approfondire la propria comprensione della materia in modo divertente.• Testa le tue competenze teoriche• Sfida te stesso con domande a scelta multipla• Apprendi nuovi concetti e applica le tue conoscenze","img":"https:/images/course6.png"}
More Quizzes
Capitolo 5
201025
Simulazione esame semiotica
3316190
CX Quiz - 17 April 20
11631
Internet safety
520
YMCA Staff Quiz Week 2
1167
Your Rodney Scout Reservation Area of Work
1368
Romeo and Juliet
1050
Anime Noob Quiz
520
Réseau de Partage contre le Gaspillage Alimentaire
420
Disha
320
Linux Quiz 2
301554
Character BATTLE! Choose your favorite characters for each of the voice actors. You can skip anyone you don't know.
1580