Theory of Computation-Finite Automata

There are ________ tuples in finite state machine.

• 4

• 5

• 6

• 7

Transition function maps.

• Σ * Q -> Σ

• Q * Q -> Σ

• Σ * Σ -> Q

• Q * Σ -> Q

Number of states require to accept string ends with 10.

• 3

• 2

• 1

• can’t be represented.

Extended transition function is

• Q * Σ* -> Q

• Q * Σ -> Q

• Q* * Σ* -> Σ

• Q * Σ -> Σ

δ*(q,ya) is equivalent to .

• δ((q,y),a)

• δ(δ*(q,y),a)

• δ(q,ya)

• independent from δ notation

String X is accepted by finite automata if .

• δ*(q,x) E A

• δ(q,x) E A

• δ*(Q0,x) E A

• δ(Q0,x) E A

Languages of a automata is

• If it is accepted by automata

• If it halts

• If automata touch final state in its life time

• All language are language of automata

Language of finite automata is.

• Type 0

• Type 1

• Type 2

• Type 3

Finite automata requires minimum _______ number of stacks.

• 1

• 2

• 0

• 3

The basic limitation of finite automata is that

• It can’t remember arbitrary large amount of information

• It sometimes recognize grammar that are not regular

• It sometimes fails to recognize regular grammar.

• All of the mentioned