GATE 1992 Theory Of Computation Topic -Finite Automata<\/p>\n
[fvplayer id=”151″]<\/p>\n
Finite Automata (FA)<\/strong> is a fundamental concept in Theory of Computation (TOC)<\/strong> and plays a key role in recognizing patterns and designing compilers. It is the simplest model of computation used to recognize Regular Languages<\/strong>.<\/p>\n A Finite Automaton (FA)<\/strong> is formally defined as a 5-tuple (Q, \u03a3, \u03b4, q\u2080, F)<\/strong>, where:<\/p>\n Q<\/strong> \u2192 Finite set of states.<\/p>\n<\/li>\n \u03a3<\/strong> \u2192 Finite set of input symbols (Alphabet).<\/p>\n<\/li>\n \u03b4 (Transition Function)<\/strong> \u2192 Mapping from (State \u00d7 Input) \u2192 State.<\/p>\n<\/li>\n q\u2080 (Start State)<\/strong> \u2192 The initial state of the automaton.<\/p>\n<\/li>\n F (Final States)<\/strong> \u2192 Set of accepting states.<\/p>\n<\/li>\n<\/ul>\n Finite Automata are classified into two types:<\/p>\n DFA and NFA are equivalent<\/strong> in power (both recognize the same set of languages).<\/p>\n States: \u2714 Explanation:<\/strong><\/p>\n Start at If Stay in Any string ending in States: Explanation:<\/strong><\/p>\n Start at If If Once in DFA is always more structured but may require more states than an equivalent NFA.<\/strong><\/p>\n Lexical Analysis in Compilers<\/strong> (Token Recognition).<\/p>\n<\/li>\n Pattern Matching<\/strong> (Regular Expressions).<\/p>\n<\/li>\n Text Searching Algorithms<\/strong> (e.g., KMP Algorithm).<\/p>\n<\/li>\n Hardware Circuit Design<\/strong> (Sequential Circuits).<\/p>\n<\/li>\n<\/ul>\n Q:<\/strong> Which of the following is true? Correct Answer: (A) Every DFA is an NFA.<\/strong> Finite Automata<\/strong> is a basic computational model that recognizes Regular Languages<\/strong>. \u00a0Would you like more solved GATE questions or examples?<\/strong><\/p>\n In the GATE 1992 Computer Science Engineering (CSE)<\/strong> exam, the Theory of Computation<\/strong> section featured questions on Finite Automata<\/strong>, focusing on regular expressions and their identities.<\/span><\/p>\n Question:<\/strong> A. r\u2217=r\u2217r^* = r^*<\/span>r<\/span>\u2217<\/span><\/span><\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>r<\/span>\u00a0Definition of Finite Automata (FA)<\/strong><\/h3>\n
\n
Types of Finite Automata<\/strong><\/h3>\n
\n\n
\n Type<\/strong><\/th>\n Description<\/strong><\/th>\n Recognizes<\/strong><\/th>\n<\/tr>\n<\/thead>\n\n \n DFA (Deterministic Finite Automata)<\/strong><\/td>\n One transition per input symbol from each state<\/td>\n Regular Languages<\/td>\n<\/tr>\n \n NFA (Nondeterministic Finite Automata)<\/strong><\/td>\n Multiple transitions for the same input symbol or \u03b5-moves<\/td>\n Regular Languages<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n \u00a0Example of DFA<\/strong><\/h3>\n
Language:<\/strong> Strings over
{0,1}<\/code> that end with 1<\/code>.<\/h3>\nDFA Representation:<\/strong><\/h3>\n
{q0, q1}<\/code>
Alphabet: {0,1}<\/code>
Start State: q0<\/code>
Final State: q1<\/code>
Transitions:<\/p>\n\n\n
\n State<\/th>\n Input 0<\/code><\/th>\nInput 1<\/code><\/th>\n<\/tr>\n<\/thead>\n\n\n q0<\/strong><\/td>\n q0<\/td>\n q1<\/td>\n<\/tr>\n \n q1<\/strong><\/td>\n q1<\/td>\n q1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n \n
q0<\/code>.<\/p>\n<\/li>\n1<\/code> is encountered, move to q1<\/code>.<\/p>\n<\/li>\nq1<\/code> if more 1<\/code>s are encountered.<\/p>\n<\/li>\n1<\/code> is accepted.<\/p>\n<\/li>\n<\/ul>\n\u00a0Example of NFA<\/strong><\/h3>\n
Language:<\/strong> Strings containing
10<\/code> as a substring.<\/h3>\nNFA Representation:<\/strong><\/h3>\n
{q0, q1, q2}<\/code>
Alphabet: {0,1}<\/code>
Start State: q0<\/code>
Final State: q2<\/code>
Transitions:<\/p>\n\n\n
\n State<\/th>\n Input 0<\/code><\/th>\nInput 1<\/code><\/th>\n<\/tr>\n<\/thead>\n\n\n q0<\/strong><\/td>\n q0<\/td>\n q1<\/td>\n<\/tr>\n \n q1<\/strong><\/td>\n q2<\/td>\n –<\/td>\n<\/tr>\n \n q2<\/strong><\/td>\n q2<\/td>\n q2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n \n
q0<\/code>.<\/p>\n<\/li>\n1<\/code> appears, move to q1<\/code>.<\/p>\n<\/li>\n0<\/code> follows, move to q2<\/code> (accepting state).<\/p>\n<\/li>\nq2<\/code>, stay there for any input.<\/p>\n<\/li>\n<\/ul>\n\u00a0Key Differences Between DFA & NFA<\/strong><\/h3>\n
\n\n
\n Feature<\/strong><\/th>\n DFA<\/strong><\/th>\n NFA<\/strong><\/th>\n<\/tr>\n<\/thead>\n\n \n Determinism<\/strong><\/td>\n One transition per input symbol<\/td>\n Multiple transitions possible<\/td>\n<\/tr>\n \n Empty Moves (\u03b5-transitions)<\/strong><\/td>\n Not allowed<\/td>\n Allowed<\/td>\n<\/tr>\n \n Complexity<\/strong><\/td>\n More states required<\/td>\n Fewer states<\/td>\n<\/tr>\n \n Conversion<\/strong><\/td>\n Easy to implement<\/td>\n Can be converted to DFA<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n \u00a0Applications of Finite Automata<\/strong><\/h3>\n
\n
\u00a0GATE 1992 Question on Finite Automata<\/strong><\/h3>\n
(A)<\/strong> Every DFA is an NFA.
(B)<\/strong> Every NFA is a DFA.
(C)<\/strong> NFA can recognize more languages than DFA.
(D)<\/strong> DFA and NFA recognize different languages.<\/p>\n
Explanation:<\/strong> DFA is a special case of NFA where each state has only one transition per input. However, both DFA and NFA recognize the same set of Regular Languages<\/strong>.<\/p>\n\u00a0Summary<\/strong><\/h3>\n
DFA<\/strong> has unique transitions, while NFA<\/strong> allows multiple transitions.
Both DFA and NFA are equivalent in power<\/strong> but differ in complexity.
Used in compilers, text searching, and pattern recognition.<\/strong><\/p>\nEvolutionary Search for Cellular Automata Logic Gates with …<\/a><\/h3>\n
GATE 1992 Theory Of Computation Topic -Finite Automata<\/a><\/h3>\n
\n\ud83d\udcd8 Sample Question from GATE 1992<\/strong><\/h3>\n
Which of the following regular expression identities are true?<\/span><\/p>\n