THEORETICAL COMPUTER SCIENCE : ALL PYQ : EXAM PREPARATION : TYBCS : SPPU

a) Write output function λ of Moore and Mealy machines.

Answer: In Moore machine, the output function is the function of current state only.

λ:Q→O

Here,

Q is the set of states.

O is the set of outputs

λ  is a function that maps each state to a specific output.

In Mealy machine, the output is function of both current state and input.

λ  :Q×Σ→O

Here,

Q is the set of states.

Σ is the set of inputs.

O is the set of outputs.

λ is a function that maps each combination of state and input to a specific output.

b) List all the proper prefixes of the string “ABCD’.

Answer: A proper prefix of a string is obtained by taking any initial segment of the string, excluding the string itself. For the string "ABCD," the proper prefixes are as follows:

A, AB, ABC

Q.) Difference between NFA and DFA.

Answer: 

Feature	Deterministic Finite Automaton (DFA)	Nondeterministic Finite Automaton (NFA)
Definition	A finite automaton where for each state, there is exactly one transition for each possible input symbol.	A finite automaton where for some state and input symbol, there can be multiple transitions leading to different states.
Transition Function	$�:�\times \mathrm{\Sigma }\to �$	$�:�\times {\mathrm{\Sigma }}_{�}\to 2^{�}$
Symbol Read	Reads one input symbol at a time.	Reads one input symbol at a time, but may have $�$-transitions (transitions without consuming input).
Acceptance Criteria	Accepts or rejects an input string based on the final state reached after processing the entire input.	Accepts an input string if there is at least one computation path that leads to a final state.
Deadlocks	DFA does not have deadlocks; each input has a unique transition.	May have deadlocks due to $�$-transitions, where no input is consumed.
Complexity	Generally simpler and easier to understand.	Can be more expressive and may represent certain languages more concisely.
Determinism	Fully deterministic; given a state and an input symbol, the next state is uniquely determined.	Allows for nondeterminism; multiple transitions for the same state and input may exist.
Representation of Languages	Some languages require exponentially larger DFAs.	Can represent some languages with smaller NFAs than required DFAs.

Q. Pumping lemma is used to show that languages is not context free. True/False.

Answer: 

False. Pumping lemma is used to show that languages are not regular.

Q. Define nullable symbol.

Answer: A symbol is considered nullable if the automaton can reach an accepting state without consuming any input symbols. There has to be a transition from a state to an accepting state without consuming any input.

Q. Give formal definition of PDA.

Answer: A PDA or Push Down Automata is a type of automaton that extends the capabilites of a Finite Automaton by adding a stack.It operates on input tape just like finite automata but it also has the access to stack through which it can push or pop symbols. It can recognize Context-Free Languages.

A PDA is defined by a 7-tuple $�=(�,\mathrm{\Sigma },\mathrm{\Gamma },�,{�}_0,�,�)$, where:

1. $�$ is a finite set of states.
2. $\mathrm{\Sigma }$ is the input alphabet.
3. $\mathrm{\Gamma }$ is the stack alphabet.
4. $�$ is the transition function, which maps $�\times (\mathrm{\Sigma }\cup \{�\})\times \mathrm{\Gamma }$ to subsets of $�\times {\mathrm{\Gamma }}^{\ast }$, where $�$ represents an empty string.
5. ${�}_0$ is the initial state.
6. $�$ is the initial stack symbol.
7. $�$ is the set of accepting states.

Q. Right Linear Grammar.

Answer: Right linear grammar or Right Regular Grammar is a type of formal grammar that generates a regular language. It consists of production rules where right hand side of production rules has a terminal string followed by non terminal symbol.

All the production rules have form , A-> xB, where A and B are non terminal symbols and x is a terminal string.

Q. State true or false. DFA do not have multiple final states.

Answer: False. DFA can have zero, one or multiple final states.

Q. State the type of language the turing machine can accept.

Answer: Turing machine can accept the language known as reursively enumerable language. It is denoted by RE or also called as Type-0 language in Chomsky hierarchy.

Q. Write the tuples of LBA.

Answer: LBA stands for linear bounded automaton, it is a type of turing machine. It is called linear bounded because it is a type of turing machine which is bounded by the input length.

It's definition includes 7-tuple:

M=(Q,Σ,Γ,δ,q0​,qaccept​,qreject​), where:

1. $�$: a finite set of states.
2. $\mathrm{\Sigma }$: the input alphabet.
3. $\mathrm{\Gamma }$: the tape alphabet, where $\mathrm{\Sigma }\subset \mathrm{\Gamma }$.
4. $�$: the transition function, which is a partial function $�:�\times \mathrm{\Gamma }\to �\times \mathrm{\Gamma }\times \{�,�\}$. It specifies the transitions between states based on the current state and symbol under the tape head, along with the movement of the tape head (left or right).
5. ${�}_0$: the initial state.
6. ${�}_{\text{accept}}$: the accepting state.
7. ${�}_{\text{reject}}$: the rejecting state.

Q. What is DFA.

Answer: It has state, input and transition function. It stands for Deterministic finite automata.

Deterministic specifies that for each input there is only one output.

It is a 5-tuple:

M= {Q, ∑,δ, q0, F}:

Q: Set of all states

 ∑: Set of all inputs.

δ: Transition function. Q x  ∑

q0: Initial State

F: Set of final states.

Q. What is Moore/Mealy machine.

Answer: It is a 6-tuple.

M= {Q, ∑, δ q0, , Δ, λ }

Q: Set of all states

∑: Set of all inputs

δ: Transition function : Q x∑

q0: It is initial state

Δ: It is set of final states

λ: It is mapping of Q x∑->  λ giving output associated with transition function..

Q. What is normal form.

Answer: It is described by a set of conditions that each rule in a grammar must satisfy.

It is of two types :

1) CNF - Chomsky Normal Form

2) GNF - Greibach Normal Form