1. (20%) Indicate whether the following statements are True or False: (a) A standard Turing machine always halts when an

[answerhappygod]

1 20 Indicate Whether The Following Statements Are True Or False A A Standard Turing Machine Always Halts When An 1 (75.61 KiB) Viewed 22 times

1. (20%) Indicate whether the following statements are True or False: (a) A standard Turing machine always halts when an input string is rejected by the machine. (b) When a standard Turing machine enters a final state, it will always stop. (c) Deterministic and nondeterministic pushdown automata are equivalent. (d) Pushdown automata always halt when there is no input. (e) Any context-free grammar with 2-free can be represented in Chomsky normal form. (f) Every s-grammar is unambiguous. (g) Any context-free language can be parsed in linear time. (h) Any string that belongs to a context-free language has a leftmost and a rightmost derivation. (i) The removing of 2-productions may introduce new unit-productions into the grammar. (j) Any context-free language can be represented in s-grammar.