Theory of Computation

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

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?

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?

Which of the following statements is/are CORRECT?

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)