CS402 Theory Of Automata
Solved Subjective Questions
For Final Term Papers
Q2- Why we use NFA instead of FA?
An NFA is a TG with a unique start state and a property of having single letter as label of transitions. An NFA is
a collection of three things
Finite many states with one initial and some final states
Finite set of input letters, say, Σ = {a, b, c}
Finite set of transitions, showing where to move if a letter is input at certain state (∧ is not a valid transition),
there may be more than one transition for certain letters and there may not be any transition for certain letters.
Q3- Define NFA.
An NFA is a TG with a unique start state and a property of having single letter as label of transitions. An NFA is
a collection of three things
Finite many states with one initial and some final states
Finite set of input letters, say, Σ = {a, b, c}
Finite set of transitions, showing where to move if a letter is input at certain state (∧ is not a valid transition),
there may be more than one transition for certain letters and there may not be any transition for certain letters.
Equivalent FAs
It is to be noted that two FAs are said to be equivalent, if they accept the same language, as shown in the
following FAs.
NFA with Null String
Definition
If in an NFA, ∧ is allowed to be a label of an edge then the NFA is called NFA with ∧ (NFA-∧).
An NFA-∧ is a collection of three things
Finite many states with one initial and some final states.
Finite set of input letters, say, Σ = {a, b, c}.
Finite set of transitions, showing where to move if a letter is input at certain state.
There may be more than one transitions for certain letter and there may not be any transition
for a certain letter. The transition of ∧ is also allowed at any state.
Q5- What is difference between FA union and FA addition?
Q5- What is difference between FA union and FA addition?
Q6- What is difference between FA concatenation and FA intersection?
Q7- Consider the language L which is EVEN-EVEN define over ∑ = {0,1} L partition ∑* into four classes and explain. (Hint- Myhill Nerode Theorem).
Q8- Why we use capital letters for language. e.g we say L is a regular language.
Non-Terminals: The symbols that must be replaced by other things are called non-terminals.
Q9- What is difference between PUSHDOWN STACK and PUSHDOWN STORE?
PUSHDOWN STACK or PUSHDOWN STORE
PUSHDOWN STACK is a place where the input letters can be placed until these letters are refered again. It can
store as many letters as one can in a long column.
Initially the STACK is supposed to be empty i.e. each of its storage location contains a blank.
PUSH
A PUSH operator adds a new letter at the top of STACK, for e.g. if the letters a, b, c and d are pushed to the
STACK that was initially blank, the STACK can be shown as
Q10- Write down five points of a conversion form of PDA.
Conversion form of PDA
Definition
A PDA is in conversion form if it fulfills the following conditions:
There is only one ACCEPT state.
There are no REJECT states.
Every READ or HERE is followed immediately by a POP i.e. every edge leading out of any READ or HERE
state goes directly into a POP state.
No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are
any intervening PUSH states (i.e. the POP states must be separated by READs or HEREs).
All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every
edge has only one label.
Even before we get to START, a “bottom of STACK” symbol $ is placed on the STACK. If this symbol is ever
popped in the processing it must be replaced immediately. The STACK is never popped beneath this symbol.
Right before entering ACCEPT this symbol is popped out and left.
The PDA must begin with the sequence
Q11- Turing machine was introduces by Alan Mathison. True
Turing machine
Definition
A Turing machine (TM) consists of the following
An alphabet Σ of input letters.
An input TAPE partitioned into cells, having infinite many locations in one direction. The input string is placed
on the TAPE starting its first letter on the cell i, the rest of the TAPE is initially filled with blanks (Δ’s).
www.allvupastpapers.blogspot.com
www.allvupastpapers.blogspot.com
Q12- The CYK algorithm converts the given CFG in CNF. True
Q13- In new format of FAs ACCEPT state is like a final state of an FA. True
Q14- A law of grammar is in reality a suggestion for possible substitutions. True
Q15- Symbols that cannot be replaced by any thing are called terminals. True
By ADEEL ABBAS, Bhakkar. AdeelAbbasbk@gmail.com
No comments:
Post a Comment
PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE
Note: Only a member of this blog may post a comment.