Theoretical Computer Science : TYBCS : SPPU : PYQs

 Chapter 1 Finite Automaton 

1 mark

Q. Finite automata has more than one final states (true or false). justify.

Answer: True. Finite automata can have more than one final state. In fact, having multiple final states is a common feature of finite automata. When the automaton reaches any of these final states after processing input, it signifies that the input string is accepted.

Q. State two differences between NFA and DFA.

Answer: Two differences between Non-Deterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA) are:

Transitions: DFA transitions are uniquely determined by the current state and input symbol. NFA transitions can have multiple choices, and the automaton can transition to multiple states on the same input.

Acceptance: In DFA, an input string is accepted if the automaton reaches a single accepting state after processing the entire input. In NFA, an input string is accepted if there is at least one path that leads to an accepting state.

Q. 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".

Q. What are proper prefixes and proper suffixes of the string "India"?

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

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

Q. 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.

Q. 

Q. 

Q. Compare λ  function of Melay and Moore machine.

Q. Construct a DFA to accept all decimal numbers divisible by 3.

Q. Construct a DFA equivalent to following NFA.

Q. Minimize the following DFA.

Q. Define NFA.

Q. Define proper suffix with help of an example.

Q. Write the mapping of λ function with Melay machine.

Q. 4. Construct a DFA to accept the set of all strings over ¥ = {a, b, ¢} such that the string

starts with ‘ac’ and not having ‘cab’ as substring in it.

Q.5. Convert the following NFA with € moves to DFA.

Q. 6. Construct a Mealy machine of a language L over ¥ = {0, 1} which outputs *$" if strin

ends with ‘aba’, outputs ‘#’ if string ends with ‘bab’, otherwise outputs **’.

1. Give the mapping of ‘&' function of NFA with € moves. :

Ans. 

2. If A={€}. Find the value of IAl .

Ans. 

3. Differentiate between Moore and Mealy machine. 

4. Construct a DFA to accept the set of all strings over X = {0, 1, 2} such that the string ends with '012' or '20'

Q. Convert the following given NFA to DFA.

Q. 6. Construct a Moore machine for a language L over ¥ = {0, 1} which outputs '$' if string ends with '100". outputs '#' if string ends with ‘001", otherwise outputs '*'. 

Q. Minimize the following DFA:

M= ({q0,q1,q2,q3,q4,q5,q6,q7}, {0, 1), sigma, qo, {q1}) where  sigma is given by:

Chapter 2 Regular Expressions and Languages 

Chapter 3 Context-Free Grammars and Languages 

Chapter 4 Push Down Automata 

Chapter 5 Turing Machine