MCQ IN COMPUTER SCIENCE & ENGINEERING

COMPUTER SCIENCE AND ENGINEERING

THEORY OF COMPUTATION

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Finite state machine can recognize language generated by ____
A
Only context free grammar
B
Only regular grammar
C
any unambiguous grammar
D
Only context sensitive grammar
Explanation: 

Detailed explanation-1: -Unambiguous grammar is the grammar that doesn’t have ambiguity i.e. does not have more than one left or rightmost derivation for an input string. Hence, language generated by the regular grammar is accepted by the finite state machines.

Detailed explanation-2: -FMS stands for Finite State Machine, which is used for recognizing the language that is generated by the regular grammar only.

Detailed explanation-3: -The language accepted (or recognized) by an FSM is the set of all strings it recognizes when used in recognition mode. The language generated by an FSM is the set of all strings it can generate when used in generation mode. The language accepted and the language generated by an FSM are exactly the same.

Detailed explanation-4: -Finite automata can be used to generate strings in a regular language. A finite automaton for a particular language is “programmed, ” in a way, to generate the strings of a given language through its states and transition functions.

Detailed explanation-5: -Finite automata are used to recognize patterns. It takes the string of symbol as input and changes its state accordingly.

There is 1 question to complete.