TALF units 2-3

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.

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

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

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.

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.

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.

True or false: If an automaton can make two different transitions with the same symbol from a certain state, then it is nondeterministic.

True or false: A DFA is connected if all states are accessible from the final state.

True or false: If Q/E2= Q/E3 , then Q/E4= Q/E5.

True or false: If pE5q then pE2q.

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.

True or false: An AF cannot recognize λ unless the initial state is final.

True or false: pTq means f(p,a)=q.

True or false: If the minimal automata of two finite automata are isomorphic, then the finite automata are equivalent.

True or false: There are certain NFA that cannot be converted into DFAs.

True or false: The language recognized by an unconnected DFA changes if we remove its inaccessible states.

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.

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.

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

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.

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.

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 pTq is satisfied, then it can be ensured that qTp. 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 pTr. 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.

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.

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

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) = $*

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.

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

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.

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.

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

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

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, …}

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

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

Given the alphabet {A, B} and the language L1 = {A, B} and L2 = {AA, BB}, which is true? a. The language L2L1 is the same as L1L2 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

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

Given an alphabet ∑ and admitting that L1 and L2 are two languages defined on ∑, TRUE? a. If x € L1L2, then x € L2 U L1 b. If x € L1 U L2, then x € L2 U L1 c. If x € L1 U L2, then x € L2L1 d. If x € L1L2, then x € L2L2

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

True or False: In an AF, f(p, lambda) = p, for all p in Q.

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

True or false: The alphabet of a finite automaton can have infinite symbols.

True or false: In an FA, if f(p, lambda) = q and f(q, lambda) = r then pT*r

True or false: If in an automata all states are final, then Q/E0 = Q/E.

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.

True or false: It is enough that f(p, lambda) = q for an automata to be non-deterministic

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.

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.

True or false: Only the FDA can recognize lambda