TOC PRACTICE QUESTIONS CFG AND PDA

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

• a) stack
  
  
  

• b) input tape

• c) terminals

• d) none of the mentioned

 A PDA machine configuration (p, w, y) can be correctly represented as:

• a) (current state, unprocessed input, stack content)

• b) (unprocessed input, stack content, current state)

• c) (current state, stack content, unprocessed input)

• d) none of the mentioned

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

• a) process the whole string

• b) end in final state

• c) end with an empty stack

• d) all of the mentioned

In a DPDA, which of the following statements is true?

• a) Each state can have at most one transition for each input symbol

• b) A state can have multiple transitions for the same input symbol

• c) There can be multiple states with no outgoing transitions

• 
  d) None of the mentioned

Which of the following is a simulator for non deterministic automata?

• a) JFLAP

• b) Gedit

• c) FAUTO

• d) None of the mentioned
  

The production of the form A->B , where A and B are non terminals is called


c

• a) Null production

• b) Unit production

• ) Greibach Normal Form

• d) Chomsky Normal Form

Inorder 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

In context to the process of removing useless symbols, which of the following is correct?

• We remove the Nullable variables

• We eliminate the unit productions

• We eliminate products which yield no terminals

• All of the mentioned

Given grammar G:

S->aS|A|C

A->a

B->aa

C->aCb

Find the set of variables that can produce strings only with the set of terminals.

• {C}

• {A,B}

• {A,B,S}

• None of the mentioned

Suppose A->xBz and B->y, then the simplified grammar would be:

• a) A->xyz

• b) A->xBz|xyz

• c) A->xBz|B|y

• d) none of the mentioned