EXAM Preparation : Theoretical Computer Science : TYBCS Sem 5

 Chapter 1: Finite Automaton

Q1) State the difference between NFA & DFA.

Answer: 

Point	DFA	NFA
Dead Configuration	Not Allowed	Allowed
Multiple Choices for an Input	Not Allowed	Allowed
Null (Epsilon) Move	Not Allowed	Allowed
Deterministic Features	Associated with real computers	Not Associated with real computers
Designing and Understanding	Difficult	Easy

Q2)  Explain the concept of prefix, suffix, proper prefix and proper suffix.

Answer: 

Prefix: A prefix of a string is any number of leading symbols of that string.

Example: x= abc, the prefixes of x are a, ab and abc. 

The prefix other than the string itself is called as proper prefix. In above example, a and ab are proper prefixes of abc.

Suffix: A suffix of a string is any number of trailing symbols in it.

Example: x= abc, the suffixes of x are c, bc and abc.

The suffix other than the string itself is called as proper suffix. In above example, c and bc are proper suffixes of abc.

Q3) What are proper prefixes and proper suffixes of the string "Computer"?

Answer: Proper prefixes of "Computer" are: "C", "Co", "Com", "Comp", "Compu", "Compute". Proper suffixes of "Computer" are: "r", "er", "ter", "uter", "puter", "omputer".

Q4)  What are proper prefixes and proper suffixes of the string "India"?

Answer: Proper Prefixes: "I", "In", "Ind","Indi"

Proper Suffixes: "ndia", "dia","ia","a"

Q5) Define DFA & NFA.

Answer:

Definition of DFA: DFA is called as Deterministic Finite Automata.

It is a 5 tuple, (Q,...)