TALF units 2-3
4.8(4)
Studied by 93 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt PlayCard Sorting
1/47
Earn XP
Description and Tags
Last updated 3:22 PM on 10/17/22
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
48 Terms
1
New cards
mark the true statements.
a. In a finite automata, there can be two initial states
b. in a finite automata, the initial state can never be the final state.
c. In a finite automata there can be more than one final state.
d. Finite automata can only recognize finite languages.
a. In a finite automata, there can be two initial states
b. in a finite automata, the initial state can never be the final state.
c. In a finite automata there can be more than one final state.
d. Finite automata can only recognize finite languages.
c
2
New cards
mark the true statements
a. if it is true that f'(p,11) = q, and f'(p,11) = p, then the AF is surely NOT deterministic
b. be an AFND(non-deterministic finite automata) in which for the word x in $* there are two different transition sequences, so that this word x is recognized by the automata (x in L(NFA)) the states it reaches by both paths must be final.
c. an NFA cannot recognize the empty word, unless the initial state is final.
d. there are NFA that can become DFA
a. if it is true that f'(p,11) = q, and f'(p,11) = p, then the AF is surely NOT deterministic
b. be an AFND(non-deterministic finite automata) in which for the word x in $* there are two different transition sequences, so that this word x is recognized by the automata (x in L(NFA)) the states it reaches by both paths must be final.
c. an NFA cannot recognize the empty word, unless the initial state is final.
d. there are NFA that can become DFA
a
3
New cards
mark the true statements
a. in a deterministic finite state, recognising the word lambda, the initial state must be final.
b. in a deterministic finite automata, the initial state can never be the final state.
c. In a finite automata there can only be one final state.
d. finite automata cannot recognize infinite languages
a. in a deterministic finite state, recognising the word lambda, the initial state must be final.
b. in a deterministic finite automata, the initial state can never be the final state.
c. In a finite automata there can only be one final state.
d. finite automata cannot recognize infinite languages
a
4
New cards
mark the true statements.
a. If an automata can make two different transitions with the same symbol from a given state, then it is NOT deterministic.
b. in an NFA it is possible to arrive, with the same input word x, from the initial state to a final state with two successions of different transitions.
c. an NFA cannot recognize the empty word unless the initial state is final.
d. there are NFA that can NOT be converted into DFA.
a. If an automata can make two different transitions with the same symbol from a given state, then it is NOT deterministic.
b. in an NFA it is possible to arrive, with the same input word x, from the initial state to a final state with two successions of different transitions.
c. an NFA cannot recognize the empty word unless the initial state is final.
d. there are NFA that can NOT be converted into DFA.
a, b
5
New cards
mark the true statements.
a. in an NFA that recognizes the empty word, the initial state must always be final.
b. A finite automata can have more than one final state.
c. in a DFA that recognizes the empty word, the initial state must always be final.
d. For an FA to recognize an infinite language, it must have a cycle in the graph that describes its transition function.
a. in an NFA that recognizes the empty word, the initial state must always be final.
b. A finite automata can have more than one final state.
c. in a DFA that recognizes the empty word, the initial state must always be final.
d. For an FA to recognize an infinite language, it must have a cycle in the graph that describes its transition function.
b, c, d
6
New cards
mark the true statements.
a. states p and q in a DFA are equivalent (p E q) if and only if for every word, x in $*, for which a final state is reached from one state (p or q) a final state will also be reached from the other state (q or p) with the same word, x in $*.
b. the states p and q of a DFA are equivalent (pEq) if and only if for every word x in $* it is true that from p and q the same state r (r in Q) is reached with the word x.
c. the final states may NOT be in the same equivalence class for Q/E0.
d. if |Q| = 3, then Q/E1 = Q/E whatever the automata.
a. states p and q in a DFA are equivalent (p E q) if and only if for every word, x in $*, for which a final state is reached from one state (p or q) a final state will also be reached from the other state (q or p) with the same word, x in $*.
b. the states p and q of a DFA are equivalent (pEq) if and only if for every word x in $* it is true that from p and q the same state r (r in Q) is reached with the word x.
c. the final states may NOT be in the same equivalence class for Q/E0.
d. if |Q| = 3, then Q/E1 = Q/E whatever the automata.
a, d
7
New cards
True or false:
If an automaton can make two different transitions with the same symbol from a certain state, then it is nondeterministic.
If an automaton can make two different transitions with the same symbol from a certain state, then it is nondeterministic.
True
8
New cards
True or false:
A DFA is connected if all states are accessible from the final state.
A DFA is connected if all states are accessible from the final state.
False
9
New cards
True or false:
If Q/E2= Q/E3 , then Q/E4= Q/E5.
If Q/E2= Q/E3 , then Q/E4= Q/E5.
True
10
New cards
True or false:
If pE5q then pE2q.
If pE5q then pE2q.
True
11
New cards
True or false:
In an FDA it is possible to get from the initial state to the final state with two different sequences of movements.
In an FDA it is possible to get from the initial state to the final state with two different sequences of movements.
True
12
New cards
True or false:
An AF cannot recognize λ unless the initial state is final.
An AF cannot recognize λ unless the initial state is final.
False
13
New cards
True or false:
pTq means f(p,a)=q.
pTq means f(p,a)=q.
False
14
New cards
True or false:
If the minimal automata of two finite automata are isomorphic, then the finite automata are equivalent.
If the minimal automata of two finite automata are isomorphic, then the finite automata are equivalent.
True
15
New cards
True or false:
There are certain NFA that cannot be converted into DFAs.
There are certain NFA that cannot be converted into DFAs.
False
16
New cards
True or false:
The language recognized by an unconnected DFA changes if we remove its inaccessible states.
The language recognized by an unconnected DFA changes if we remove its inaccessible states.
False
17
New cards
Indicate which of the following statements related to Deterministic Finite Automata is true:
a. All DFA=($, Q, f, q0, F) where the F=Q recognizes the Universal Language $*.
b. Every DFA=($, Q, f, q0, F) whose initial state is also final recognizes the Universal Language.
c. Every DFA=($, Q, f, q0, F) in which there is no sink state recognizes the Universal Language.
d. It is not possible to build an AFD that recognizes the Universal Language.
a. All DFA=($, Q, f, q0, F) where the F=Q recognizes the Universal Language $*.
b. Every DFA=($, Q, f, q0, F) whose initial state is also final recognizes the Universal Language.
c. Every DFA=($, Q, f, q0, F) in which there is no sink state recognizes the Universal Language.
d. It is not possible to build an AFD that recognizes the Universal Language.
a
18
New cards
Indicate which of the following statements is true:
a. The symbols of an alphabet can never be made up of more than one character.
b. The empty language is that which contains the empty word.
c. The universe of discourse contains an infinite number of words.
d. The word length of the empty word is 1, ie |lambda|=1.
a. The symbols of an alphabet can never be made up of more than one character.
b. The empty language is that which contains the empty word.
c. The universe of discourse contains an infinite number of words.
d. The word length of the empty word is 1, ie |lambda|=1.
c
19
New cards
Given an alphabet $ and assuming that L1 and L2 are two languages defined on å, indicate which of the following statements is true:
a. If x in L1 then x in L1•L2
b. If x in L1•L2 then x in L1 or x in L2
c. If x in L1 then x in L1 U L2
d. If x in L1•L2 then x in L2•L1
a. If x in L1 then x in L1•L2
b. If x in L1•L2 then x in L1 or x in L2
c. If x in L1 then x in L1 U L2
d. If x in L1•L2 then x in L2•L1
c
20
New cards
Indicate which of the following statements is true:
a. For two states p and q of a DFA to be equivalent, it is essential that both states
be final states.
b. Two states p and q of a DFA are said to be equivalent of order n if for all x in $* / |x| < = n is
verifies that f'(p,x) in F --> f'(q,x) in F.
c. Every AFD=($, Q, f, q0, F) in which it is verified that |Q/E0|=1, is minimum.
d. If two states p and q of a finite automaton satisfy p in q, then it can be ensured that
both are equivalent.
a. For two states p and q of a DFA to be equivalent, it is essential that both states
be final states.
b. Two states p and q of a DFA are said to be equivalent of order n if for all x in $* / |x| < = n is
verifies that f'(p,x) in F --> f'(q,x) in F.
c. Every AFD=($, Q, f, q0, F) in which it is verified that |Q/E0|=1, is minimum.
d. If two states p and q of a finite automaton satisfy p in q, then it can be ensured that
both are equivalent.
b
21
New cards
Indicate which of the following statements is true:
a. For two deterministic finite automata to be isomorphic, it is essential that both
be minimal.
b. For two deterministic finite automata to be equivalent it is necessary that both be
minima.
c. If two deterministic finite automata are isomorphic then it is safe to say that they recognize the same language.
d. Every DFA in which from the initial state it is possible to transit to a final state is connected.
a. For two deterministic finite automata to be isomorphic, it is essential that both
be minimal.
b. For two deterministic finite automata to be equivalent it is necessary that both be
minima.
c. If two deterministic finite automata are isomorphic then it is safe to say that they recognize the same language.
d. Every DFA in which from the initial state it is possible to transit to a final state is connected.
c
22
New cards
Indicate which of the following statements is true:
a. Every finite automaton for which p exists in Q / f(p, λ)=p is an NFA.
b. If p and q are states of an NFA and pT*q is satisfied, then it can be ensured that qT*p.
c. If p, q and r are states of an NFA and it is satisfied that f(p,l)=q and f(q, l)=r, then we can
ensure that pT*r.
d. Given an AFND=($, Q, f, q0, F) and a word x in $*, x is said to be accepted by the NFA if f”(q0,x) contains at least one state and that state is different from q0.
a. Every finite automaton for which p exists in Q / f(p, λ)=p is an NFA.
b. If p and q are states of an NFA and pT*q is satisfied, then it can be ensured that qT*p.
c. If p, q and r are states of an NFA and it is satisfied that f(p,l)=q and f(q, l)=r, then we can
ensure that pT*r.
d. Given an AFND=($, Q, f, q0, F) and a word x in $*, x is said to be accepted by the NFA if f”(q0,x) contains at least one state and that state is different from q0.
c
23
New cards
Indicate which of the following statements is true:
a. The language {00, 001, 1001} can be generated from the alphabet {0, 01}.
b. If x is any word in a language and xi is the ith power of that word, then
it is satisfied that |x ^ i |=|x|^i.
c. Every alphabet generates an infinite number of words.
d. The word concatenation operation satisfies the commutative property.
a. The language {00, 001, 1001} can be generated from the alphabet {0, 01}.
b. If x is any word in a language and xi is the ith power of that word, then
it is satisfied that |x ^ i |=|x|^i.
c. Every alphabet generates an infinite number of words.
d. The word concatenation operation satisfies the commutative property.
c
24
New cards
Given an alphabet $ and assuming that L1 and L2 are two languages defined on $, indicate which of the following statements is false:
a. If x in L1 then x in L1 U L2
b. If x in L1 then x in L1•L2
c. If x in L1 U L2 then x in L2 U L1
d. If lambda in L1•L2 then lambda in L1 and lambda in L2
a. If x in L1 then x in L1 U L2
b. If x in L1 then x in L1•L2
c. If x in L1 U L2 then x in L2 U L1
d. If lambda in L1•L2 then lambda in L1 and lambda in L2
b
25
New cards
Given a DFA=($, Q, f, q0, F) indicate which of the following statements is false:
a. If x in L(DFA) then f'(q0, x) in F
b. If q0 on F then lambdal on L(AFD)
c. If F={Ø} then L(AFD) = lambda
d. If F=Q then L(AFD) = $*
a. If x in L(DFA) then f'(q0, x) in F
b. If q0 on F then lambdal on L(AFD)
c. If F={Ø} then L(AFD) = lambda
d. If F=Q then L(AFD) = $*
c
26
New cards
Indicate which of the following statements is false:
a. Given an alphabet, the Universal Language contains an infinite number of words.
b. The symbols that make up an alphabet can be made up of several characters.
c. The word length is a quantity dependent on the alphabet on which the word is defined.
word.
d. To ensure that the empty word (lambda) belongs to the Universal Language of an alphabet, it is necessary to know the symbols that make up said alphabet.
a. Given an alphabet, the Universal Language contains an infinite number of words.
b. The symbols that make up an alphabet can be made up of several characters.
c. The word length is a quantity dependent on the alphabet on which the word is defined.
word.
d. To ensure that the empty word (lambda) belongs to the Universal Language of an alphabet, it is necessary to know the symbols that make up said alphabet.
d
27
New cards
Indicate which of the following statements is true:
a. The language {00, 001, 1001} can be generated from the alphabet {0, 01}.
b. The word concatenation operation satisfies the commutative property.
c. Every alphabet generates an infinite number of words.
d. If x is any word in a language and xi is the ith power of that word, then
it is satisfied that | x^i |=|x|^i
a. The language {00, 001, 1001} can be generated from the alphabet {0, 01}.
b. The word concatenation operation satisfies the commutative property.
c. Every alphabet generates an infinite number of words.
d. If x is any word in a language and xi is the ith power of that word, then
it is satisfied that | x^i |=|x|^i
c
28
New cards
Indicate which of the following statements related to Deterministic Finite Automata is true:
a. Every DFA=($, Q, f, q0, F) whose initial state is also final recognizes the Universal Language.
b. Every DFA=($, Q, f, q0, F) in which there is no sink state recognizes the Universal Language.
c. All DFA=($, Q, f, q0, F) where the F=Q recognizes the Universal Language, $*.
d. It is not possible to build a DFA that recognizes the Universal Language.
a. Every DFA=($, Q, f, q0, F) whose initial state is also final recognizes the Universal Language.
b. Every DFA=($, Q, f, q0, F) in which there is no sink state recognizes the Universal Language.
c. All DFA=($, Q, f, q0, F) where the F=Q recognizes the Universal Language, $*.
d. It is not possible to build a DFA that recognizes the Universal Language.
c
29
New cards
Indicate which of the following statements is true:
a. For two deterministic finite automata to be isomorphic, it is essential that both
be minimal.
b. If two deterministic finite automata are isomorphic then it is safe to say that they recognize the same language.
c. For two deterministic finite automata to be equivalent it is necessary that both be minimal.
d. Every DFA in which from the initial state it is possible to transit to a final state is connected.
a. For two deterministic finite automata to be isomorphic, it is essential that both
be minimal.
b. If two deterministic finite automata are isomorphic then it is safe to say that they recognize the same language.
c. For two deterministic finite automata to be equivalent it is necessary that both be minimal.
d. Every DFA in which from the initial state it is possible to transit to a final state is connected.
b
30
New cards
Select the TRUE option:
a. Given a DFA, the number of equivalence classes in Q/E0 is always 2
b. Two automata are equivalent if their initial states are equivalent in their direct sum
c. The number of states of a DFA always is equal to the number of equivalence classes in Q/E
d. For two FA to be equivalent it is necessary that they have the same number of states
a. Given a DFA, the number of equivalence classes in Q/E0 is always 2
b. Two automata are equivalent if their initial states are equivalent in their direct sum
c. The number of states of a DFA always is equal to the number of equivalence classes in Q/E
d. For two FA to be equivalent it is necessary that they have the same number of states
a
31
New cards
Indicate which of the following is FALSE:
a. The word length is a quantity dependent on the alphabet on which the word is defined
b. The symbols that make up an alphabet can be made up of several characters
c. Given an alphabet, the Universal Language contains an infinite number of words
d. To ensure that the empty word belongs to the Universal Language of an alphabet, it is necessary to know the symbols that make up the alphabet
a. The word length is a quantity dependent on the alphabet on which the word is defined
b. The symbols that make up an alphabet can be made up of several characters
c. Given an alphabet, the Universal Language contains an infinite number of words
d. To ensure that the empty word belongs to the Universal Language of an alphabet, it is necessary to know the symbols that make up the alphabet
d
32
New cards
Given the alphabets ∑1 = {ab, e} and ∑2 = {a} select the TRUE option, wrt L = W (∑1 U ∑2) * ∑1*∑2:
a. L = {λ, ab, e, a, abe, aba, eab, ea, aab, …}
b. L = {ab, e, a, abe, aba, eab, ea, aab, …}
c. L = {aba, ea, ababa, eaba, abea, eea, aaba, aea, …}
d. L = {λ, abab, abe, aba, eab, ee, ea, abeab, abee, abea, …}
a. L = {λ, ab, e, a, abe, aba, eab, ea, aab, …}
b. L = {ab, e, a, abe, aba, eab, ea, aab, …}
c. L = {aba, ea, ababa, eaba, abea, eea, aaba, aea, …}
d. L = {λ, abab, abe, aba, eab, ee, ea, abeab, abee, abea, …}
d
33
New cards
Given the DFA = {∑, Q, f, q0, F}, indicate the FALSE statement
a. To make sure that p€Q is accessible from itself, it is mandatory that the DFA is connected
b. If q0€F, then λ belongs to the language recognized by the DFA
c. Given {p,q}€Q, p is accessible from q if ⱻ x€∑* so f’(q,x) = p
d. If all states in Q are accessible from q0, then the DFA is connected
a. To make sure that p€Q is accessible from itself, it is mandatory that the DFA is connected
b. If q0€F, then λ belongs to the language recognized by the DFA
c. Given {p,q}€Q, p is accessible from q if ⱻ x€∑* so f’(q,x) = p
d. If all states in Q are accessible from q0, then the DFA is connected
a
34
New cards
Given the DFA = {∑, Q, f, q0, F}, indicate the FALSE statement
a. If L is the language recognized by a DFA and F ≠󠄾 empty, then, L ≠ empty
b. Given x€∑*, it is said that x is recognized by the DFA if f’ (q0, x) € F
c. The language associated to the DFA is composed by all the words x/x€∑* and f’ (q0, x)
d. If F = Q, then the language recognized by the DFA is the Universal Language
a. If L is the language recognized by a DFA and F ≠󠄾 empty, then, L ≠ empty
b. Given x€∑*, it is said that x is recognized by the DFA if f’ (q0, x) € F
c. The language associated to the DFA is composed by all the words x/x€∑* and f’ (q0, x)
d. If F = Q, then the language recognized by the DFA is the Universal Language
c
35
New cards
Given the alphabet {A, B} and the language L1 = {A, B} and L2 = {AA, BB}, which is true?
a. The language L2*L1 is the same as L1*L2
b. The word AABB is included in the language L1 U L2
c. L2 includes an infinite number of words
d. L2 is always included in L2 U L1
a. The language L2*L1 is the same as L1*L2
b. The word AABB is included in the language L1 U L2
c. L2 includes an infinite number of words
d. L2 is always included in L2 U L1
d
36
New cards
Which is FALSE?
a. The empty word is one whose length is zero
b. A word is defined as a finite sequence of symbols of an alphabet
c. Given an alphabet, the universe of discourse is made up of a finite set of words
d. Word length is defined as the number of alphabet symbols that make up that word
a. The empty word is one whose length is zero
b. A word is defined as a finite sequence of symbols of an alphabet
c. Given an alphabet, the universe of discourse is made up of a finite set of words
d. Word length is defined as the number of alphabet symbols that make up that word
c
37
New cards
Given an alphabet ∑ and admitting that L1 and L2 are two languages defined on ∑, TRUE?
a. If x € L1*L2, then x € L2 U L1
b. If x € L1 U L2, then x € L2 U L1
c. If x € L1 U L2, then x € L2*L1
d. If x € L1*L2, then x € L2*L2
a. If x € L1*L2, then x € L2 U L1
b. If x € L1 U L2, then x € L2 U L1
c. If x € L1 U L2, then x € L2*L1
d. If x € L1*L2, then x € L2*L2
b
38
New cards
Given the DFA = {∑, Q, f, q0, F}, indicate the TRUE statement
a. For every p, q€F, pEq
b. If p, q€{Q} and pE2q, then pE0q
c. For every p, q€{Q} - {F} pE1q
d. If |Q|=6 and p, q €{Q} are in equivalence relation pE3q, then pEq
a. For every p, q€F, pEq
b. If p, q€{Q} and pE2q, then pE0q
c. For every p, q€{Q} - {F} pE1q
d. If |Q|=6 and p, q €{Q} are in equivalence relation pE3q, then pEq
b
39
New cards
True or False:
In an AF, f(p, lambda) = p, for all p in Q.
In an AF, f(p, lambda) = p, for all p in Q.
True
40
New cards
True or false:
In an NFA it is possible to get from the initial state to a final state with two different sequences of movements
In an NFA it is possible to get from the initial state to a final state with two different sequences of movements
True
41
New cards
True or false:
The alphabet of a finite automaton can have infinite symbols.
The alphabet of a finite automaton can have infinite symbols.
False
42
New cards
True or false:
In an FA, if f(p, lambda) = q and f(q, lambda) = r then pT*r
In an FA, if f(p, lambda) = q and f(q, lambda) = r then pT*r
True
43
New cards
True or false:
If in an automata all states are final, then Q/E0 = Q/E.
If in an automata all states are final, then Q/E0 = Q/E.
True
44
New cards
True or false:
If the final states of an FA1 and FA2 do not belong to the same class in the Q/E of the automata sum, then AF1 and AF" are not equivalent.
If the final states of an FA1 and FA2 do not belong to the same class in the Q/E of the automata sum, then AF1 and AF" are not equivalent.
False
45
New cards
True or false:
It is enough that f(p, lambda) = q for an automata to be non-deterministic
It is enough that f(p, lambda) = q for an automata to be non-deterministic
True
46
New cards
True or false:
Suppose that automaton FA1 recognizes the words {x, y, z} and automaton FA2 recognizes the words {x,y,z, w}. It can be stated that FA2 is equivalent to FA1, since it recognizes its language.
Suppose that automaton FA1 recognizes the words {x, y, z} and automaton FA2 recognizes the words {x,y,z, w}. It can be stated that FA2 is equivalent to FA1, since it recognizes its language.
False
47
New cards
True or false:
If p and q are in the same class in Q/E1 and, furthermore, f(p,a) and f(q,a) are also in the same class (for any word a), then p and q belong to the same class in Q/E2.
If p and q are in the same class in Q/E1 and, furthermore, f(p,a) and f(q,a) are also in the same class (for any word a), then p and q belong to the same class in Q/E2.
True
48
New cards
True or false:
Only the FDA can recognize lambda
Only the FDA can recognize lambda
False
Note 
Flashcards (44)