FA
Deterministic Finite Automata
What is DFA?
The symbols from the input alphabets and the operators(+,*,.) Forms the regular expression
Define regular expression ?
PDA is powerful
Which is more powerful? PDA or FA
Context Sensitive Grammar
What is the language accepted by LBA?
If we use TAPE as stack then it will be a PDA
How TM can be simulated as PDA
NFA is more powerful
Which is more powerful? DFA or NFA
Regular Language
Regular expression are used to represent which language?
Variables and terminals
Which type of symbols contain in the stack of PDA?
Non deterministic Turing Machine
LBA is deterministic or non deterministic TM?
Recursively Enumerable Language
What is the language accepted byTM?
For each input there will be a single transition from each state. But in NFA for each input there can be more than one transition from each state
Difference between DFA and NFA
Union,concatenation,closure
Which of the following operations can be applied on regular expression?
Present state
String to be processed
Stack symbol
The ID of PDA shows
Sa->aSa
Give some examples for context Sensitive Grammar?
If we make TAPE finite then it will be a FA
How TM can be simulated as FA
Mealy machine
In which Transducer output depends on current state and current input
0(0+1)0
The set of all strings over 0,1 in which all strings that begins and ends with 0?
Stack symbol
What is Z0?
LBA is more powerful.
Which is more powerful? LBA or PDA
A language is recursive if it is decided by a TM.
What is recursive language?
Moore machine
Transducer whose outputs are determined by its current state
Pumping lemma theorem for regular Language.
Which theorem is used to prove that the given language is not regular?
In CFG, LHS should have single non terminal,
RHS will be a combination of terminal and non terminal or terminals or non terminals
But is CSG, Both LHS and RHS Can be a combination of terminals and non terminals
Difference between CFG and CSG?
End markers restricts the computations to constant bounded area
What is the use of end markers in LBA?
If TAPE size is equal to input size then it will be LBA
How TM can be simulated as LBA