# Theory Of Computation MCQ - Regular languages and finite automata

26:

Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a, b } ?

 A. a* b* B. (a | b)* C. (ab)+ D. (a  | b*) Answer Report Discuss Option: B Explanation : Click on Discuss to view users comments. Write your comments here:
27:

An FSM (Finite State Machine) can be considered to be a TM (Turing Machine) of finite tape length

 A. without rewinding capability and unidirectional tape movement. B. rewinding capacity, and unidirectional tape movement C. without rewinding capability and bidirectional tape movement D. rewinding capability and bidirectional tape movement Answer Report Discuss Option: A Explanation : Click on Discuss to view users comments. Write your comments here:
28:

Palindromes can't be recognized by any FSM because

 A. FSM can't remember arbitrarily large of information B. FSM can't deterministically fix the mid-point C. even if mid-point is known, FSM be can't be found  whether, second half of the string matches the first half D. all of these Answer Report Discuss Option: D Explanation : Click on Discuss to view users comments. Write your comments here:
29:

If ∑ =  {a, b, c, d, e, f } then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is

 A. 35 B. 360 C. 49 D. 720 Answer Report Discuss Option: B Explanation : Here string length is 4 so we can create  string of length 4 by 6 values. Suppose at first place we can arrange any value  by 6 methods.so 6. then Remaining total numbers  are 5 so we can arrange them by 5 methods at second place. then remaining total numbers are 4 so we can arrange them  by 4 methods. now remaining total numbers are 3 and we can arrange them by 3 methods. so according to permutation technique. We multiply them i.e. 6*5*4*3=360. So, 'B' Click on Discuss to view users comments. richa said: (4:19pm on Saturday 13th April 2013) this answer comes out... 6!c(6-4!)*4! vikki gound said: (2:09am on Thursday 23rd May 2013) thus answer of given question is total no of string=6!=720and length of each string=6-4=2 then we calculate length of string=(6c2)*4!=15*24=360so total length=720-360=360 Write your comments here:
30:

A language L is accepted by a finite automaton if and only if it is

 A. context - free B. context-sensitive C. recursive D. Right-linear Answer Report Discuss Option: D Explanation : Click on Discuss to view users comments. Write your comments here: