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

$$\mathrm{letter\to[A-Za-z]}$$

$$\mathrm{letter\to[0-9]}$$

$$\mathrm{id\to letter(letter\,|\,digit)^*}$$

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

Which of the following statements is/are CORRECT?

Consider the context-free grammar G below

$$\matrix{ S & \to & {aSb|X} \cr X & \to & {aX|Xb|a|b,} \cr } $$

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?

Consider the pushdown automation (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {$$\bot$$, 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 $$\in $$, 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 $$\bot$$ in it. The PDA accepts by empty stack.

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