For each
1. T
2. T
3. T
4. T
5. T
6. T
7. T
8. T
9. T
10. T
11. T
12. T
13. T
14. T
15. T
16. T
17. T
18. T
19. T
20. T
21. T
22. T
23. T
24. T
25. T
26. T
27. T
28. T
29. T
30. T
31. T
32. T
33. T
34. T
35. T
36. T
37. T
38. T
39. T
40. T
41. T
42. T
of the F F F F F F F F F F F F F F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
Prep for Quiz 7
following statements, circle whether it is True or False: There is a TM that accepts { an, where n = 2i with i 1 }. Every Turing Machine M decides a language L.
All regular languages are recursive.
All context-free languages are recursive.
The union of two recursive languages is recursive.
The intersection of two recursive languages is recursive.
All Turing Machines have some input on which they run forever. Every Turing Machine accepts some language.
Every language is decided by some Turing Machine.
Every language is accepted by some Turing Machine.
All Turing Machines eventually halt on input .
Every regular language is decided by some Turing Machine.
Every context free language is accepted by some Turing Machine.
If there is a TM which accepts a language L, then there must be a TM
which decides L.
A TM can have an infinite number of states.
If L is a CFL then there is a TM which decides L.
A language can be both decidable and undecidable.
The language { aibjckdlemfn : i, j, k, l, m, n 1 } is recursive.
A PDA and DPDA may be equivalent.
A type 0 language is always inherently ambiguous.
The empty string is always in the empty language.
The context-free languages are a proper subset of the context-sensitive languages. An infinite language contains only strings of finite length.
Every language generated by a type 3 grammar is Turing-acceptable.
Every language generated by a type 2 grammar is Turing-acceptable.
Every CFL can be described by an infinite number of context-free grammars. Every subset of a regular language is regular.
TMs always either halt or loop forever.
Every derivation corresponds to a unique parse tree, and vice-versa.
Any infinite regular language properly contains another infinite regular language. Every subset of a context-free language is context-free.
If L1 L2 is regular, then both L1 and L2 must also be regular.
The empty string is never in the empty language.
If L(G) is infinite, then G is not a regular grammar.
If L(G) is finite, then G is a regular grammar.
The intersection of two CFLs is context-free.
A PDA with two independent stacks is equivalent to the TM model.
Nonregular languages are always infinite.
Nondeterminism adds no power to deterministic finite automata.
An infinite language contains an infinite number of strings.
Nondeterminism adds no power to deterministic PDAs.
Nondeterminism adds no power to deterministic Turing machines.
each problem/question/language below is Decidable (D) or Undecidable (U). [Note: A Page 1 of 2
Circle whether
problem/question/language is either Decidable (D) or not Decidable (D).]
1. D U
2. D U
3. D U
4. D U
5. D U
6. D U
7. D U
8. D U
9. D U
10. D U
11. D U
12. D U
13. D U
14. D U
15. D U
16. D U
17. D U
18. D U
19. D U
20. D U
21. D U
22. D U
23. D U
24. D U
25. D U
26. D U
27. D U
28. D U
Whether an arbitrary TM accepts all even-length strings. Whether an arbitrary TM halts on all input.
Whether an arbitrary TM in the course of a computation revisits the starting cell (i.e., the cell under the read-write head at the beginning of the computation).
Whether two arbitrary TMs M1 and M2 accept the same language, i.e., L(M1) = L(M2).
Whether two arbitrary nfa’s M1 and M2 accept the same language, i.e., L(M1) = L(M2).
Whether an arbitrary TM starting with a blank tape will ever write a nonblank symbol anywhere before halting.
Whether an arbitrary TM halts on at least two strings w and x within some number of steps s, such that s < 1000 and s is prime.
Given an arbitrary TM M that always halts and any integer n > 0, whether or not an L(M).
Given an unrestricted grammar G and string w, whether G generates w.
Whether any arbitrary context-free grammar is ambiguous.
Whether two arbitrary regular expressions describe the same language.
Whether an arbitrary TM begun on a completely blank tape halts in at most 1010 steps. Whether an arbitrary TM starting with a blank tape will ever halt.
Whether an arbitrary TM with given input will ever return to its initial state. Whether two arbitrary PDAs generate the same language.
Whether an arbitrary PDA rejects every string over its alphabet.
Whether an arbitrary dfa accepts a finite or an infinite language.
Whether you (in particular) will graduate from CSUN by 2022.
Whether an arbitrary TM, when operating on input w, never moves to the right on two consecutive moves.
Whether two arbitrary CFGs generate the same language.
If G is a CFG, whether or not L(G) is regular.
Whether two arbitrary CFGs G1 and G2 satisfy: L(G1) L(G2).
For an arbitrary unrestricted grammar G, determine whether or not L(G) is empty.
The membership problem for an arbitrary recursively enumerable language.
Whether an arbitrary Turing machine M accepts a finite number of strings, i.e., L(M) is finite.
Whether two arbitrary CFGs G1 and G2 satisfy: L(G1) L(G2) = .
Whether an arbitrary CFG G1 and regular grammar G2 satisfy: L(G2) L(G1). Whether an arbitrary CFG G1 and regular grammar G2 satisfy: L(G1) L(G2)= .
Page 2 of 2