Automata Flashcard April 2025

Front

Turing machine is more powerful than: Finite Automata, Push Down Automata

Back

Both A and B

Front

A Turing machine operates over

Back

infinite memory tape

Front

The Current State is S1 and Input is 1 What is the OUTPUT and Direction Options: 1, L; 1, R; 0, L; 0, R

Back

1, R

Front

What is the form of productions in a context free grammar G in Chomsky normal form?

Back

A → BC or A → A

Front

The context free grammar S → A111|S1, A → A0 | 00 is equivalent to

Back

{0ⁿ1ᵐ | n=2, m=3}

Front

The context free grammar S → SS | 0S1 | 1S0 | ɛ generates

Back

Equal number of 0's and 1's

Front

State which of the following statements is true?

• If L(G1) and L(G2) are equivalent, even then it is not necessary that they are of same type
• A context free language is also a regular language
• A context sensitive language is also a context free language
• None of the mentioned

Back

If L(G1) and L(G2) are equivalent, even then it is not necessary that they are of same type

Front

The transition a Push down automaton makes is additionally dependent upon the:

Back

stack

Front

With reference of a DPDA, what do we perform from the start state with an empty stack?

Back

All of the mentioned (process the whole string, end in final state, end with an empty stack)

Front

In order to simplify a context free grammar, we can skip the following operation:

• Removal of null production
• Removal of useless symbols
• Removal of unit productions
• None of the mentioned

Back

None of the mentioned