Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Theoretical Computer Science > Theory - Automata And Grammar > Flashcards

Theory - Automata And Grammar Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What are formal models? When a model is considered adequate?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the phases of software engineering?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the importance of using formal language and models in the specification and design phases?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the differences between discrete and continuous models?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the differences between operational and descriptive models?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What can we use languages for?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are translations and some practical examples of it?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the relationship between languages, systems, properties and problems?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What kind of model is a finite state machine?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the difference between languages and alphabets?

A

An alphabet, by following a grammar, generates a language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a drawback of FSM?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the Pumpkin Lemma?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What properties of a FSA that makes the cardinality of a language equals to infinity possible?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When is a language considered closed with respect to a given operation?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are regular languages?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What operations are regular languages closed under?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How can we determine the intersection between two FAs?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How can we determine the union between two FSAs?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How can we design the FSA of the complementary language of a language given the FSA of the latest? What is the condition for such strategy to work? How can we solve the possible problem?

A

By switching terminal states and non terminal states

In order for it to work we need the delta function to be complete

If given a FSA we do not have the delta function complete, we just need to complete it adding the transitions that were not there and adding a state for non acceptance conditions

20
Q

How can we determine the union between 2 FSA?

A
21
Q

How can a PDA recognize a^n b^n language, and why it can not recognize a a^n b^n c^n language?

A
22
Q

The family language recognized by PDAs are not closed under which operations?

A
23
Q

What are Turin machines?

A
24
Q

What relations exist among the various automata (TM in particular) and more traditional/realistic computing models?

A
25
Q

How does a NDFA accepts? Slide 90

A
26
Q

Describe the negative consequence of pumping lemma

A
27
Q

How can we design an FSA for the complement language?

A
28
Q

What is the family of languages recognized by PDAs?

A
29
Q

What family of languages TMs accept?

A
30
Q

Solve the following problem:

L = {w e {a,b}*|#a>=2, #b<=1}

A
31
Q

Solve the following problem:

L = {w e {a,b}*|#a>=2, #b>=1}

A
32
Q

Solve the following problem:

L = {w e {0,1,2}|w is a ternary string encoding a number written with base 3}

A
33
Q

Solve the following problem:

L = {w e {0,1,2}|w is a ternary string encoding a number written with base 3}

No more than 1 zero to the left? Check

A
34
Q

Solve the following problem:

L = {w e {0,1}*|w has an equal number of occurrences of the substrings “10” and “01”}

A
35
Q

Solve the following problem:

L = {w e {0,1}*|w has an equal number of occurrences of the substrings “100” and “001”}

A
36
Q

Solve the following problem:

L = (0+1)*00 ? Check

A
37
Q

Solve the following problem:

L = (01+010)*

A
38
Q

Design a PDA to recognize a^n b^n | n>0

A
39
Q

Formalize the representation of a PDA

A
40
Q

Formalize the transition of a PDA more the transition relation

A
41
Q

How can we prove the PDA is more expressive/Powerfull than FSA

A

Showing that we can write any FSA as a PDA just not using the stack (pop and push Z0)

42
Q

How can we prove that PDAs are not closed under union?

A

a^n b^n

a^n b^2n

43
Q

How can we prove PDAs are not closed under intersection?

A

a^m c^n b^n

a^n c^n b^m

44
Q

Why is the initial configuration of a Turin Machine

A
45
Q

Formalize the definition of a TM

A
46
Q

Formalize the transition of a TM plus the transition state? -|

A
47
Q

Design a TM to recognize the a^n b^n c^n | n>0 language

A

Theoretical Computer Science (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions