Test: Automata - Computer Science Engineering (CSE) MCQ

A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.

The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.

Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.

• Statement 1: True. Finite automata can be represented graphically using state diagrams.


• Statement 2: True. In these diagrams, nodes represent the different states of the automaton.


• Statement 3: True. Edges or arcs are used to depict transitions between states based on input symbols

All statements are correct. Finite automata utilize nodes and edges similar to graph structures to visualize state transitions, enhancing understanding and analysis.

According to the question, minimum of 3 states are required to recognize an octal number divisible by 3.

Explanation: A FA can be represented as FA= (Q, ∑, δ, q0, F) where Q=Finite Set of States, ∑=Finite Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).

 A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.

∑r= {1,0} and a Kleene* operation would lead to the following set=COUNT{ε,0,1,00,11,01,10} =7.

We need minimum n+1 states to build NFA that accepts all substrings of a binary string. For example, following NFA accepts all substrings of “010″ and it has 4 states.

Explanation: ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.