Page 1 of 1
1. (20%) Indicate whether the following statements are True or False: (a) A standard Turing machine always halts when an
Posted: Mon Jun 06, 2022 6:50 pm
by 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 23 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.