Întrebare Baok

Ciurse & Braoch : CSE Semester: 6

Subiect: Theiry dacă Cimputatio SubiectCide: CST-352

Ni. dacă studenț i: 960 Regular/ Reappear:Regular

Nite:1. Completaț i corect detaliile din tabelul de mai sus.

2. Nu ș tergeț i/mutaț i pozi ț ia capitolului ș i nivelul său de dificultate în formatul de mai jos al băncii de întrebări.

3. Scrie întrebarea făcând un capitol virtual al Unită ț ii (dacă unitatea nu este împăr ț ită în capitole) ș i corespunzător
nivelul de dificultate în celula corespunzătoare astfel încât din fiecare capitol să poată fi selectată întrebarea pentru teste.
4. Pentru întrebările de tip răspuns lung, se solicită ș efilor de departament să decidă câte subpăr ț i sunt necesare pentru
cursul lor adică 2 subpărț i sau 3, ț inând cont de nivelul întrebării.
5. Toate subpăr ț ile, ecua ț iile, imaginile, dacă există, trebuie să fie plasate în aceea ș i celulă a tabelului pentru acela ș i lucru.
întrebare.
6. Nu lăsa ț i nici o celulă goală
7. Nu repeta întrebarea care ar putea conduce la întrebări duplicate în Test
8. Nu repeta aceea ș i întrebare atât în varianta scurtă, cât ș i în cea de răspuns lung.

Întrebări de tip Răspuns Scurt

 Întrebare
Nr. crt. Întrebare
Tip

Unitatea -1 Construiț i un automat finit pentru expresia regulată 0(1+0)*

1

Unitatea -1 Oferiț i DFA-ul care acceptă limbajul peste alfabetul 0, 1 care are setul tuturor ș irurilor.
2
începând cu 10.

Consideraț i automatul finit ale cărui diagramă de tranziț ie este dată mai jos, verificaț i dacă 110001
va fi acceptat sau respins de maș ină.

Unitatea -1
3

Unitatea -1 Write the difference between the Kleene closure and Kleene plus.
4

Unitatea -1 Construiț i un DFA pentru limbajul tuturor ș irurilor în care fiecare 0 este urmat imediat de 1.
5
 Unitatea -1 Give English descriptions of the languages of the regular expression (0+1)(0+1)*.
6

Unitatea -1 If L is a set of all strings over {a, b} startng with a. Find Complement of L and Reversal of L.
7

Unitatea -1 dacă L={a,bb}, găseș te

8

Unitatea -1 Fiecare DFA este NDFA. Justifică această afirmaț ie.

9

Unitatea -1 Dacă L este mulț imea tuturor ș irurilor peste {0,1} care se termină cu 01, găsiț i expresia regulată corespunzătoare.
10

Unitatea -2 Construiț i o CFG pentru limbajul ș irurilor palindromice de lungime impară peste {a, b}.
11

Unitatea -2
Arătaț i că id+id*id poate fi generat de două derivate stânga distincte în
12 grammar E->E+E | E*E | (E) | id

Unitatea -2 Menț ionaț i aplicaț ia CFG.

13
 Unitatea -2 What are the two normal forms of CFG?
14

Fie G gramatică S->aB/bA,A->a/aS/bAA,B->b/bS/aBB. Obț ineț i arborele de analiză pentru

Unitatea -2
15 ș irul aaabbabbba

Unitatea -2 Legea Pompei de Stat.

16

Unitatea -2 Differentiate between Finite Automaton with output and without output with example.
17

Unitatea -2
Lăsaț i producț ia gramaticii să fie S-> 0B | 1A, A-> 0 | 0S | 1AA, B-> 1|1S |0BB. Pentru
18 ș ir 0110 găseș te derivarea cea mai din dreapta

Unitatea -2
Construct a derivaton tree for the string 0011000 using the grammar S->A0S |0 | SS ,
19 A-> S1A|1

Unitate -2 Scrieț i CFG pentru limbajul L = (anbn| n>1)

20

Unitatea-3 Oferiț i un exemplu de limbaj liber de context non-determinist.

21
 Unit-3 Oferiț i un exemplu de un limbaj care este CFL, dar nu limbaj regulat.
22

Unitatea-3 Diferenț iaț i între miș carea benzii PDA ș i miș carea benzii maș inii Turing.
23

Unitatea-3 Menț ionaț i două probleme care pot fi rezolvate doar de TM, dar nu de PDA.
24

Unitatea-3 Give an example of Type 2 grammar.

25

Unitatea-3 Oferiț i corelaț ia dintre gramatică ș i limbi.

26

Unitatea-3 List out applicatons of PDA.

27

Unitatea-3 Scrieț i despre rolul stivei în Automat de tip Push Down.

28

Unitatea-3 Stati problema MPCP.

29
 Unitatea-3 Stabileș te Problema PCP.
30

Tip întrebări Liog Aoswer

Sr. Întrebare
Întrebare
Nu Tip

Construi ț i DFA pentru a accepta următoarele limbi peste alfabetul {0, 1}

Unitatea -1
1
Medie a) Limbajul tuturor ș irurilor care conț in cel puț in trei 1-uri.
b) Limbajul tuturor ș irurilor care nu se termină cu 11.
c) Limbajul tuturor ș irurilor care conț in un număr par de 1.
d) Limbajul tuturor ș irurilor care conț in un număr de 1-uri divizibil cu 4
e) Limbajul tuturor ș irurilor de lungime două.

Dacă setul de simboluri de intrare conț ine {0,1} ș i limba dată conț ine toate ș irurile care încep cu
cu 1 ș i fără a avea două 0-uri consecutive.
Unitatea -1
2 (a) Construieș te o expresie regulată care să satisfacă constrângerile menț ionate mai sus.
Medie
(b) De asemenea, construiț i un FA echivalent cu expresia regulată creată la pasul (a).

3 Unitatea -1 Describe five tuples of DFA and construct a DFA equivalent to the NFAM=({p,q,r},{0,1}, δ ,p,
Medie {q,s})
unde δ este definit în următorul tabel
 0 1

P {q,s} {q}

Întrebare {r} {q,r}

R {s} {p}

S - {p}

4 Unitatea -1 (a) Construie ș te un DFA care acceptă toate ș irurile w peste {0,1} astfel încât numărul de 1 în w să fie 3
Medie mod 5.
(b) Identifica ț i stările ini ț iale ș i finale în NDFA M dat mai jos ș i arăta ț i de asemenea dacă acceptă
un ș ir 01110 sau nu.
 ["Scrie cinci tuple ale Automanului Finite Nondeterminist.","De asemenea, converteș te următorul NFA."]
la un DFA

Q\Σ 0 1

P {p,q} P
Unitatea -1
5
Medie

Întrebare r R

R s -

S s S

6 Unitatea -1 Sunt DFA ș i NDFA echivalente în putere? Dacă da, construieș te un automat determinist.
 echivalent cu NDFA reprezentat de tabelul prezentat mai jos:

Medie

Unitatea -1 Diferentiaț i între DFA, NDFA ș i NDFA cu tranziț ii nule. De asemenea, explicaț i cele 5 tupluri ale acestora.
7
Medie maș ini în detaliu.

(a) Oferi ț i no ț iunea de acceptare a unui ș ir de către un Automat Finit Determinist.

(b) Construie ș te un DFA echivalent cu NFA dat mai jos

Unitatea -1
8
Medie

Convertiț i următorul NDFA/NFA în DFA, a cărui tabel de tranziț ii este dat.

Q= {q0q1q2,q3}, ∑={a,b}. Aici q0este starea iniț ială ș i q3este starea finală.

Unitatea -1
9
Medie

Explică
în procedură pas cu pas.
 State Arden’s theorem. Also find the regular expression corresponding to the given automaton

Unitatea -1
10
Medie

Construieș te un DFA echivalent cu NDFAM a cărei diagramă de tranziț ie este dată mai jos

Unitatea -1
11
Dificil

Defineș te expresiile regulate ș i construieș te un DFA echivalent cu expresia regulată

Unitatea -1 (0+1)*(00+11)(0+1)*
12
Dificil

Oferiț i semnificaț ia operatorilor + ș i * în expresiile regulate ș i construiț i un FA echivalent cu

Unitatea -1 expresia regulată
13
Dificil
11+ (1+00)0*1.
 a) Cum se deosebe ș te NFA de NFA cu tranzi ț ii nule.
b) Construi ț i un NFA care acceptă limbajul reprezentat de expresia regulată

Unitatea -1
14
Dificil

((0+1)*11)+ 0*1)

The transiton table of a nondeterministc finite automatonMis defined by Construct a

automatul finit determinist echivalent cu M

Unitatea -1
15
Dificil

M=({q1, q2, q3},{0,1}, funcț ia de tranziț ie, q1, {q3}) este un automat finit nedeterminist
Automat unde funcț ia de tranziț ie este dată de

Unitatea -1
-16
Dificil

Construieș te un DFA echivalent

17 Unitatea -1 Găsiț i expresia regulată pentru automatul finit al cărui diagramă de tranziț ie este prezentată mai jos
Dificil ș i arată că acceptă mulț imea tuturor ș irurilor peste alfabetul {a, b} cu un număr egal de
a'si b's, astfel încât fiecare prefix să aibă cel mult cu unul mai mult decât b's ș i cel mult un b mai mult
decât a Theei.
 Descrie în engleză mulț imea acceptată de automatul finit al cărui diagramă de tranziț ie este
aratat mai jos

Unitatea -1
18
Dificil

De asemenea, reprezentaț i limbajul acceptat de acest FA prin expresie regulată.

Enunț a teorema lui Arden ș i construieș te o expresie regulată corespunzătoare diagramei de stare.
descris de

Unitatea -1
19
Dificil
 Given transiton diagram below represents a DFA. Justfy this statement and find the regular
expresia corespunzătoare unei Automat Finite.

Unitatea -1
20
Dificil

Unitatea -1
Formulează teorema lui Kleene ș i construieș te automatul finit echivalent cu expresia regulată.
21 10+(0+11)0*1.
Dificil

Pentru fiecare dintre următoarele limbi, daț i o expresie regulată

Unitatea -1
22
Dificil

23 Unitatea -1 În fiecare parte de mai jos, desenaț i un FA care acceptă limbajul indicat peste {a, b}
Dificil
 a) Limbajul tuturor ș irurilor care con ț inexact două a-uri.
b) Limbajul tuturor ș irurilor care con ț in cel pu ț in două a-uri.
c) Limba tuturor ș irurilor care nu se termină cu ab.
d) Limbajul tuturor ș irurilor care încep cu aa.
e) Limbajul tuturor ș irurilor care con ț in substringul aa.

In each part below, draw an FA acceptng the indicated language over {a, b}

Unitatea -1
24
Dificil a) Limbajul tuturor ș irurilor în care atât numărul de a-uri cât ș i numărul de b-uri
sunt pare.
b) Limba tuturor ș irurilor în care fiecare a (dacă există) este urmat de
imediat, bye.
c) Limbajul tuturor ș irurilor care con ț in sub ș iruri aba

(a) Proiectaț i DFA pentru următoarele pe ∑={a,b}

i. Toate ș irurile având un număr impar de b-uri ș i terminând cu a.
ii. Toate ș irurile care conț in substringul bb.

Unitatea - 1
25 (b) Reprezentaț i următoarele mulț imi prin expresii regulate:
Dificil
(i) {⋀,111, 111111, 111111111…..}
(ii) The set of all strings over{a, b}beginning and ending withb.
(iii) Mulț imea tuturor ș irurilor peste {0, 1} care conț ine cel puț in un zero.

Identifică tipul de ș iruri în următoarele limbi ș i oferă expresia regulată corespunzătoare.

expresie reprezentând mulț imea.
Unitatea -1
26
Dificil
 Găseș te limba reprezentată de următoarele expresii regulate

Unitatea -1
27
Dificil

Reprezentaț i următoarele mulț imi prin expresii regulate

Unitatea -1
28
Dificil

Studiază automatul M (ț inând cont de ca stare iniț ială) dată mai jos ș i starea dacă
Afirmaț iile a)-e) sunt adevărate sau false cu o justificare adecvată:

Unitatea -1
29
Dificil

a) M este un automat nedeterminist.

b) 0100111 este acceptat de M.
c) 010101010 nu este acceptat de M.

d)
e) O ș ir de caractere care are un număr par de 0-uri este acceptat de M.
 Construiț i diagrama de tranziț ie corespunzătoare expresiilor regulate

Unitatea -1 (a) (ab+c*)*b

30
Dificil (b) a+bb+bab*a

Mulț imea limbajelor regulate este închisă sub următoarele operaț ii

a) Uniune
b) Concatenare
c) Kleene *
Unitatea -2 d) Kleene +
31
Medie e) Intersec ț ie
diferen ț ă
g) Complement

Justifică cu un exemplu potrivit.

a) Definirea formală a Gramaticii prin 4 tuple

Unitatea -2 b) Descrie corela ț ia dintre gramatică (G) ș i limba generată de gramatică (L(G))
32 printr-un exemplu potrivit.
Medie
c) Diferentia ț i între Forma Normală Chomsky ș i Forma Normală Greibach
 Diferenț iaț i între gramaticile ambigue ș i cele neambigue ș i demonstraț i că următoarele
gramaticile sunt ambigue

Unitatea -2
33 a) E->E+E/E*E/(E)/id
Medie b) S->SS/(S)/a/ ∧

Găsiț i o gramatică redusă echivalentă cu gramatica G prin eliminarea simbolurilor inutile ale căror
Unitatea -2 produsele sunt
34
Medie

Construiț i o gramatică redusă prin eliminarea simbolurilor inutile echivalente cu gramatica

Unitatea -2
35
Medie

Stabiliț i reguli pentru a elimina producț iile nul din CFG. Consideraț i gramatica G al cărei producț ii
sunt
Unitatea -2
36
Medie
Eliminaț i produsele nule din această gramatică dată

37 Unitatea -2 Stabiliț i reguli pentru a elimina producț iile unitate. Consideraț i gramatica G a cărei producț ii sunt
Medie
Elimină producț iile unitate ș i obț ine o gramatică echivalentă.
 Unitatea -2
Formally define Moore and Mealy Machine and explain difference in output functons of two
38 maș ini printr-un exemplu potrivit.
Average

Give Rules for convertng Context Free grammar into Chomsky Normal Form Grammar(CNF).
Unitatea -2
De asemenea, converteș te gramatica dată în CNF.
39
Medie

Unitatea -2
40
Medie

În fiecare caz de mai jos, găsiț i o gramatică liberă de context fără producț ii nule care generează ...
aceeaș i limbă, cu excepț ia posibilităț ii de nul, ca CFG-ul dat

Unitate -2
41
Dificil

42 Unitatea -2
Dificil

a) Ilustra ț i limbile regulate cu un exemplu

 b) Folosind proprietă ț ile de închidere ale limbajelor regulate, demonstrează că dacă L este regulat, atunci
complementul lui L este de asemenea regulat. Demonstrează-ț i punctul cu un exemplu adecvat de DFA.
c) Cum po ț i dovedi că o limbă dată nu este regulată prin Lemma Pumping? Notează
paș i corespunzători.

Discută teorema Myhill-Nerode pentru minimizarea DFA-ului dat mai jos

Unitatea -2
43
Dificil

Identifică variabilele/nenormale ș i terminalele în gramatica dată

Unitatea -2
44
Dificil
De asemenea, găsiț i o gramatică în CNF echivalentă cu această gramatică

Construiț i o gramatică în formă normală Greibach echivalentă cu gramatica

Unitatea -2
45
Dificil

46 Unitatea -2 Folosind lema pomparei, arătaț i că următoarele seturi nu sunt regulate.

Dificil
 Unitatea -2
47
Dificil

Unitatea -2 Oferă reguli pentru a converti CFG în GNF. Explică cu un exemplu potrivit.
48
Dificil

Unitatea -2
49
Dificil

Unitatea -2 Demonstrează că setul palindromelor nu este un limbaj regulat folosind lema de pompare.
50
Dificil

Unitatea -2
51
Dificil

Unitatea -2
52
Dificil

53 Unitatea -2 Construiț i un automat cu stări minime echivalent cu DFA-ul descris ca

Dificil
 Construiț i automatul cu stări minime echivalent cu diagrama de tranziț ie

Unitatea -2
54
Dificil

55 Unitatea -2 Construiț i un automat de stări minim echivalent cu automatul finit descris de

Dificil
 Consideraț i o maș ină Mealy

Unitatea -2
56
Dificil

a) Construie ș te tabelul de tranzi ț ie pentru această ma ș ină Mealy dată

b) Găsi ț i ie ș irea pentru inputul 001
c) Construi ț i o ma ș ină Moore echivalentă cu această ma ș ină Mealy

57 Unitatea -2 Consideraț i maș ina Moore descrisă de tabela de tranziț ie dată de tabel. Găsiț i ieș irea pentru
Dificil ș ir de intrare 001 ș i construieș te maș ina Mealy corespunzătoare
 Consideraț i maș ina Mealy descrisă mai jos. Construiț i o maș ină Moore.

Unitatea -2
58
Dificil

Oferiț i paș ii pentru a converti o maș ină Moore într-o maș ină Mealy ș i construiț i o maș ină Mealy care este
echivalent cu maș ina Moore dată de Tabel

Unitatea -2
59
Dificil

60 Unitatea -2 Consideraț i maș ina Moore descrisă de tabelul de tranziț ie dat de tabel.
Dificil
 a) Desena ț i un diagramă de tranzi ț ie echivalentă din tabelul dat
b) Construie ș te ma ș ina Mealy corespunzătoare ș i reprezint-o prin tabela de tranzi ț ii ș i
diagramă de tranziț ie

Unitatea -3 Proiectaț i o Maș ină Turing peste {a,b} care acceptă {a, b}* {aba} {a, b}*
61
Medie

Unitatea -3 O DFA poate reț ine o cantitate finită de informaț ii, dar un PDA poate reț ine o cantitate infinită.
62 amount of information. Justify your answer with suitable example.
Medie

Desenaț i diagrama bloc a maș inii Turing ș i reflectaț i fiecare dintre componentele sale alegând unele potrivite.
Unitatea -3
63 exemplu
Medie

FA nu acceptă, iar PDA acceptă expresia dată:

Unitatea -3 {L= anbn| n >=1}.
64
Medie Comentariul prin luarea unui exemplu potrivit.

65 Unitatea -3 Construiț i un PDA care acceptă limbajul

Medie
 L={wcwr|w∊{a,b}+}

Unitatea -3 Desenaț i diagrama bloc a Automatonului cu Stivă ș i reflectaț i fiecare dintre componentele sale.
66
Medie exemplu potrivit

Construiț i un PDA care acceptă limbajul

Unitatea -3
67
Medie L={ancmbn|n,m> = 1}

Unitatea -3 Construct PDA which accepts all strings with equal number of a’s and b’s
68
Medie

Unitatea -3
69 Construiț i un PDA care acceptă toate ș irurile cu numărul de a-uri mai mare decât numărul de b-uri.
Medie

Unitatea -3 Trasaț i un diagramă ordonată ș i curată ș i explicaț i în detaliu corelaț ia dintre limbi ș i
70 gramatici în Ierarhia Chomsky.
Mediu

Unitatea -3 Proiectaț i o maș ină Turing care acceptă setul palindromelor.

71
Dificil

Unitatea -3 Proiectaț i un PDA pentru a accepta un limbaj {L= | n >=1}

72
Dificil
 Unitatea -3 Oferiț i un exemplu de limbaj liber de context care nu este regulat, de asemenea, proiectaț i un automaton cu stivă.
73
Dificil Automatul acceptând limba.

Unitatea -3 Discutati despre Automat Non-determinist cu Stivă, cu un exemplu potrivit.

74
Dificil

Unitatea -3 Oferiț i tuplele unui automat cu stivă determinist ș i explicaț i cu un exemplu potrivit.
75
Dificil

Discutaț i despre acceptarea PDA cu un exemplu adecvat.

Unitatea -3
76
Dificil
i. De la stiva goală la starea finală.
ii. De la starea finală la stiva goală

Diferentiaț i între următoarele

Unitatea -3 a) DFA ș i PDA

77
Dificil b) PDA ș i Ma ș ini Turing
 Construieș te un PDA care acceptă limbajul
Unitatea -3
78 L={anb2n|w∊{a,b}+}
Dificil

Unitatea -3 Construieș te un PDA care acceptă limbajul

79
Dificil L={anb3n|w∊{a,b}+}

Unitatea -3 Proiectaț i un TM pentru a accepta limbajul LE={anbncn| n >= 1 }

80
Dificil

Unit -3 Oferiț i tupluri de Maș ini Turing ș i explicaț i cu un exemplu potrivit.

81
Dificil

Construiț i un PDA care acceptă toate ș irurile cu un număr de a-uri mai mic decât numărul de b-uri.
Unitatea -3
82
Dificil

Unitatea -3 Discutarea clasificării maș inilor ș i a limbajelor acceptate de aceste maș ini, aș a cum a fost dată de Chomsky.
83
Dificil

Unitatea -3 Proiectaț i o Maș ină Turing pentru a accepta limbajul L={0n1n/n>=1}

84
Dificil

85 Unitatea -3 Găsiț i cel mai înalt număr de tip care poate fi aplicat la următoarele
Dificil productons:
 Unitatea -3 Construiț i o Maș ină Turing care recunoaș te limbajul {wcw / w∈{a, b}}+}
86
Dificil

Definiț i formal gramaticile următoare cu exemple adecvate. De asemenea, numiț i limbajul generat.
prin aceste gramatici.

Unitatea -3
87 a) Gramatici sensibile la context
Dificil
b) Gramatica neselectivă

Diferentiate între următoarele

Unitatea -3
88
Dificil
a) Limbaje recursive ș i limbaje recursive enumerabile.
b) PDA Determinist ș i Non-determinist
c) Ma ș ini Turing deterministe ș i non-deterministe

Unitatea -3
89 Proiectaț i o maș ină Turing care acceptă {ss | s ∊ {a, b}*}
Dificil
 Unitatea -3 Construiț i un PDA care acceptă limbajul
90
Dificil L={wwr|w∊{a,b}+}