Which of the following statement is not true about finite automata? a. It is a s
ID: 3837754 • Letter: W
Question
Which of the following statement is not true about finite automata?
a. It is a simple idealized machine used to recognize patterns within input taken from some alphabet.
b. It accepts or rejects an input depending on whether the pattern defined by the FA occurs in the input.
c. An FA consists of a finite set of states, a start state, a set of final states, a set of transitions from one state to another labeled with valid characters
d. An FA can detect a pattern from an infinitely long input string
e. Every pattern defined by an FA may not have an equivalent definition in RE (or vice versa)
2. Which of the following statement is true about the "test_graph_01" FA:
a. All strings must end with a "b"
b. All string must start with a "b" and end with a"b"
c. All string must contain an "a"
d. All string may pr may not conatin "a" but they have to end with a "b"
e. None of the above
3. Which of the following statement is false about the "test_graph_01" FA:
a. "a" is a valid string for the model.
b. the set of final states is F = (2).
c. The start state is 1.
d. "bbbabbb" is a valid string for the model.
e. All of the above statements are true.
4. What is an equivalent regular expression for the "test_graph_01" FA: "
a. RE = b*ab*
b. RE = (a|b)*
c. RE = ab+
d. RE = (|b)* (a|) (|b)*
5. Which of the following statement is false about the "test_graph_01" FA: "
a. All the accepted strings contain even number of a's and even number of b's.
b. The set of b's.
c. All the accepted string contain equal number of a's and b's.
d. An accepted string cannot contain “aa” or “bb” as a substring
e. The length of an accepted string is always an even number
6. What is an equivalent regular expression for the “test_graph_02” FA:
a. (a|b)
b. (a|b)*ab(a|b)*
c. (ab*|ba*)
d. (ab | ba)^+
e. (ab)^+ | (ba)^+
7. What is not True about the regular expression: (ab|ba)^*
a. It cannot contain consecutive a’s or consecutive b’s
b. It accepts an empty string
c. The length of an accepted string is even
d. An equivalent RE is (a(ab)*b | b(ba)*a|E)^+
e. All of the above statements are True
8. A language L1 accepts all strings starting with an ‘a’. Language L2 accepts all strings starting with a ‘b’. We want to define a new language L3 that can either start with an a or a b. How can we use L1 and L2 to define L3?
a. L3=L1|L2
b.L3= L1L2
c.L3= L2L1
d.L3= L2L1|L1L2
e. none of the above
9. Define a grammar to accept strings with equal number of 0’s and 1’s where a valid string is equal to 1^n0^n, n > 0
a. S ®1S0|E
b. S ® 1S0|10
c. S ®10|E
d. S ®1S0|10|E
e. S ® 1S0|0S1|E
10. Which string proves that the given grammar is ambiguous?
Grammar : S= E|SS|(S)
a. ()
b. (())
c. () ()
d. all of them
e. none of them
11. Which are possible terminal symbols for the grammar S=E|SS|(S):
a. T = {E, (,)}
b. T= {S}
c. T= {S,E,(,)}
d. T= {E, (,),®}
e. none of the above
12. Find the yield expressed in the given parse tree.
a. SSSSAS
b. (a())
c. S ®(S) ® (SS) ® (A(S)) ® (a(E))
d. S
e. A
13. Predict a subset of terminal symbols of the grammar that is used in the parse tree:
a. { (,),a}
b.{A,S}
c.{(,), E, a}
d. {S}
e. It cannot be guessed from a parse tree
14. Which of the following the production rules cannot be directly inferred from the given parse tree:
a. S ® A
b. S ® E
c. S ® SS
d. S ® a
e. S ® (S)
15. Which of the following statements is not true?
a. Every NP-Complete problem is an NP problem
b. Every NP problem can be reduced to an NP-complete problem in polynomial time
c. A solution to an NP problem is verifiable in polynomial time
d. It is not proved whether NP is closed under complement or not
e. Turing’s Halting problem is an NP-Complete problem
16. P and Q are two propositions where
P: “Mary will buy a car.”
Q: “Mary loves to drive.”
Interpret the statement P ® Q in English:
a. If Mary loves to drive, then it implies that she will buy a car.
b. If Mary buys a car, then it implies that she loves to drive.
c. Mary will buy a car but she does not love driving
d. Either Mary will buy a car or she loves driving
e. If Mary does not buy a car, then we know for sure that she does not love driving.
17. Which of the following statements is a tautology, provided that p, and q are some propositions?
a. p ® q = q ® p
b. p ^ 1 ^-p
c. p o 1
d. all of the above
e. none of the above
18. Find a truth assignment for the given expression
-(p ^ q) V –q
a. p=1, q=1
b. p=1, q=0
c. p=0, q=1
d. p=0, q=0
e. b, c, and d
19. Which one is a contradiction?
a. p ® q = q ® p
b. p ^ 1 ^-p
c. p o 1
d. all of the above
e. none of the above
test graph 01 test graph 02 Parse TreeExplanation / Answer
a. "a" is a valid string for the model.
b. the set of final states is F = (2).
c. The start state is 1.
d. "bbbabbb" is a valid string for the model.
Option a is correct. a. RE = b*ab*. As,All strings must end with a "b", As, according to figure, String must complete with b and b can come as many times.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.