Brainscape's Knowledge GenomeTM

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


See full index

Huji 67521 Computability > Models - Automata and Regular Languages > Flashcards

Models - Automata and Regular Languages Flashcards

1
Q

Define a formal language. What do ∑ and ∑ * have to do with this?

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

Define a deterministic finite automaton

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

Define the language of an automation

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

Define a regular language

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

How is a Nondeterministic finite automaton different from a DFA?

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

Define a Nondeterministic finite automaton

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

Define the language of a nondeterministic finite automaton

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

What can you say about the language of a DFA vs. the language of a NFA?

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

What is the pumping lemma for regular languages?

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

What is the intuition behind why the pumping lemma for regular languages is true?

A

L is regular so it has an automation A. We’ll take a word w that is longer than the number of states in A. -> a state in A must repeat itself in the run of A on the w (pigeon whole). -> the chain of letters between the repeating states could be erased or multiplied - and A will still conclude in an accepting state.

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

What can the pumping lemma be used to prove? How is this done?

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

The addition of a tail of any characters will either put both words into the language or exclude them both. That is, the tail works the same way on both words.

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

What is the Myhill–Nerode theorem?

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

How can you prove that an automation is minimal?

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

We have seen in class that the class REG (regular languages) is closed under what operations?

A

REG is closed under:

  1. Union
  2. Intersect
  3. Complement
  4. Concatenation
  5. Kleen star.
  6. XOR (proved in test)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What seems to you to be the easiest way to prove on a test that a language is in REG?

A

If possible, use closure properties of REG if it seems like the alternative is drawing a complex automata.

22
Q

What are examples of non-regular languages?

A
23
Q

How would you prove that a language is not regular?

A

Show that there are an infinite number of MN equivalence classes. (How?)

24
Q

Prove the minimality of the DFA in the picture.

A
25
Q
A
26
Q

Please give 7 examples of regular languages.

A

Regular Languages

  1. The empty language.
  2. Every finite language.
  3. Every language that can be expressed with a regex.
  4. For example: (ab)*
  5. L = {w | w is of even length}
  6. L = {w | #a(w) is even/odd and/or #b(w) is even/odd}
  7. Pref(L) if L is regular.

Pref(L) = every word in sigma* s.t

there exists a y in sigma* s.t wy is in L.

(A simple example of a language that is not regular is the set of strings { anbn | n ≥ 0 })

27
Q

What is the difference between the two automations described in the picture?

A
28
Q

Please summarize the ways you can prove that a language L is regular.

A
  1. Use closure properties – for example, prove that L-complete is regular. (Reg is closed under union, intersect, complement, concatenation, Kleen star)
  2. Use MN.
  3. Remember that every finite language is regular.
  4. Prove there exists the relevant DFA/NFA.
29
Q
A
30
Q

What is the principal of the DFA minimization algorithm?

A
  1. Divide the DFA into 2 groups - the accepting states and the rejecting states.
  2. check that all 1 (and then all 0) arrows either always stay within the group or always exit the group.
  3. if they do you are done. if they don’t, split the group you are observing into 2 groups so that they do.
  4. in the end - each state in the minimum DFA represents a MN equivalence class. The representative of the class could be any word that could be achieved ending at that state.
31
Q
A
32
Q

After making a DFA to prove a language is regular, what should you do to check that the DFA is not wrong?

A
  1. After going over a list of cases that should be rejected or accepted and ensuring that the DFA works correctly on those test cases, try to: run along the DFA trying to make it accept a bad word.
  2. Try to find more MN equivalence classes than the number of states in the DFA. If you succeeded - the DFA is incorrect.
33
Q

How long does it take to run the minimizing algorithm on a DFA?

A

Polynomial time.

34
Q

What is one way to prove that a language L is not in RE?

A

One can prove a language L is not in RE by showing a mapping reduction from a language not in RE to L.

35
Q
A
36
Q

How would you show that the language “Modifies(L)” is regular?

A
  1. Show a DFA for modified(L).
  2. Bound the number of MN equivalence classes for modified(L) as shown in the picture.
37
Q

What should you so if asked to proove whether something is true or false, and you know the answer but don’t know how to prove it?

A

Explain formaly how you got to the answer. In the case in the picture for example - that was the proof!

38
Q

What is a good way to go about solving questions such as this?

A

Here the trick was to look seperately at each component of the the language in question (Mark(L)), and most importantely, at the two sides of the “and” symbol (and then use closure properties of REG).

39
Q

How would you go about answering this, and proving your answer?

A

Use the DFA of the other language (draw a general scetch of it) to build a NFA “A” for the language in question. Prove that L(A) = L by showing that each side of the equasion is contained in the other.

40
Q
A
41
Q

How can you divide non regular languages in to 2 categories.

What languages are in the second categorie?

A
  1. languages over an alphabet with more than 1 letter.
  2. languages over an alphabet with a single letter.
42
Q

What are the first 3 words in the language:

a^(n^2)?

A

{epsilon (for n=0), a (for n=1), a^4… }

43
Q

Is the language of all palindromes over a certain alphabet regular?

A

The claim is true only for alphabets with more than one letter. Note that all the palindromes over sigma = {1} = (1)* which is regular.

44
Q

Draw the DFA of L.

A

Note that if the the word you are checking, at the point that you are up to, did not complete the bad substring but contains at its current point the first few letters of the bad substring - then you have to return to the point in the DFA that corresponds to being after the first few letters of the bad substring.

45
Q
A
46
Q

2018 Moed b. Hard question in my opinion.

A

Note:
The automat that remembers if a run passed through a particular state basically copies the original DFA (so every state is of the form Qi0 or Qi1), passing through the particular state switches to the Qi1s route. The accepting states are only the states in F that end in 1.
So: It is possible for a DFA to remember whether a run on a word passed through a certiain states
2. The trick here was that instead of explicitely building the whole DFA that accepts L, the problem was broken up into the intersection of smaller DFAs.

47
Q
A

Note that the language (ab)-star is over the alphabet Sigma = {a,b,c,d,e}

48
Q

How long does it take to turn an NFA into a DFA?

A

Exponential time

49
Q

When turning an NFA into a DFA, what should you do if a certain state in the DFA you are creating does not go anywhere with a certain letter?

A

You should have that letter send to a state that rejects all further input (an un-accepting state with a loop to itself for all letters).

50
Q

When turning an epsilon-NFA “A” into an NFA A’ without epsilons, how are the starting states and the accepting states in A’ determined?

A

The starting states will be the starting states from A as well as all the states in A that can be reached from an original starting state with an epsilon.

The accepting states will be the original accepting states as well as all the states in A that can reach an accepting state in A using only epsilons.

For how to turn an e-NFA into an NFA:
https://www.youtube.com/watch?v=WSGcmaHNBFM
(Note there is a small mistake there regarding the accepting states, and the rule for accepting states is as I explained above.)

Huji 67521 Computability (5 decks)

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