Question 1 |

Consider the language L over the alphabet {0, 1}, given below:

L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}.

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.

L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}.

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.

3 | |

4 | |

5 | |

6 |

Question 1 Explanation:

Question 2 |

Consider the pushdown automaton (PDA) P below, which runs on the input alphabet \{a,b\}, has stack alphabet \{ \perp ,A\}, and has three states \{s,p,q\}, with s being
the start state. A transition from state u to state v , labelled c/X/\gamma , where c is
an input symbol or , X is a stack symbol, and \gamma is a string of stack symbols,
represents the fact that in state u, the PDA can read c from the input, with X on
the top of its stack, pop X from the stack, push in the string \gamma on the stack, and
go to state v. In the initial configuration, the stack has only the symbol \perp in it.
The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by P?

Which one of the following options correctly describes the language accepted by P?

\{ a^mb^n |1\leq m\text{ and }n \lt m \} | |

\{ a^mb^n |0 \leq n \leq m \} | |

\{ a^mb^n |0\leq m\text{ and } 0 \lt n \} | |

\{ a^m |0\leq m \} \cup \{b^n|0 \leq n \} |

Question 2 Explanation:

Question 3 |

Consider the context-free grammar G below

S\rightarrow aSb \;| \;X

X\rightarrow aX \;| \;Xb \;|\; a\;|\; b

where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S.

Which one of the following statements is CORRECT?

S\rightarrow aSb \;| \;X

X\rightarrow aX \;| \;Xb \;|\; a\;|\; b

where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S.

Which one of the following statements is CORRECT?

The language generated by G \text{ is }(a + b)^* | |

The language generated by G \text{ is } a^*(a + b)b^* | |

The language generated by G \text{ is }a^*b^*(a + b) | |

The language generated by G is not a regular language |

Question 3 Explanation:

Question 4 |

Which of the following statements is/are CORRECT?

The intersection of two regular languages is regular. | |

The intersection of two context-free languages is context-free. | |

The intersection of two recursive languages is recursive. | |

The intersection of two recursively enumerable languages is recursively enumerable. |

Question 4 Explanation:

Question 5 |

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:

letter \rightarrow [A-Za-z]

digit \rightarrow [0-9]

id \rightarrow letter (letter\;| \;digit)^*

Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

letter \rightarrow [A-Za-z]

digit \rightarrow [0-9]

id \rightarrow letter (letter\;| \;digit)^*

Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

A | |

B | |

C | |

D |

Question 5 Explanation:

There are 5 questions to complete.

Two options of Q15 are the same.