Ch.11: Turing Machines II

Week 11 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 11.1. Variants of Turing Machines 11.2. Universal Turing Machine 11.3. Decidable Languages 11.4. Acceptance and Emptiness Problems

60 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

  1. [Variants of Turing Machines] What does it mean that the different variants of Turing machines are computationally equivalent?

    They recognize the same languages. Each variant (doubly infinite tape, several tapes, two-dimensional tape, nondeterminism) can be simulated by a standard TM with a semi-infinite tape.

  2. [Variants of Turing Machines] Does a TM with a doubly infinite tape (infinite in both directions) recognize more languages than a TM with a semi-infinite tape?

    No. A TM with a semi-infinite tape can simulate it.

  3. [Variants of Turing Machines] How does the book store the contents of a doubly infinite tape on a semi-infinite tape?

    Divide the tape in two: write a left-end marker $\text{\textdollar}$ , the right part, a separator #\## , the left part, and an end marker %\%% . Example: the tape …□ a b c d e f □…\dots \square\, a\, b\, c\, d\, e\, f\, \square \dots…□abcdef□… divided between ccc and ddd becomes

  4. [Variants of Turing Machines] A doubly infinite tape …□ a b c d e f □…\dots \square\, a\, b\, c\, d\, e\, f\, \square \dots…□abcdef□… is stored on a semi-infinite tape as $ d e f # a b c %\text{\textdollar}\, d\, e\, f\, \#\, a\, b\, c\, \%$def#abc% .What does the simulating TM do when it reads $\text{\textdollar}$ ?

    It moves right all the way to %\%% , then one cell left, and returns to the same state. Reading $\text{\textdollar}$ means the head moved left from ddd . On the original tape the cell left of ddd holds ccc , which is the cell just left of %\%% .

  5. [Variants of Turing Machines] A doubly infinite tape …□ a b c d e f □…\dots \square\, a\, b\, c\, d\, e\, f\, \square \dots…□abcdef□… is stored on a semi-infinite tape as $ d e f # a b c %\text{\textdollar}\, d\, e\, f\, \#\, a\, b\, c\, \%$def#abc% .What does the simulating TM do when it reads #\## ?

    It treats #\## like a blank □\square□ . The symbol #\## moves as the input expands and contracts.

  6. [Variants of Turing Machines] What is a multitape Turing machine?

    A TM with several tapes, each with its own head for reading and writing. Initially the input is on tape 1 and the other tapes are blank.

  7. [Variants of Turing Machines] How does a TM with one semi-infinite tape simulate a multitape TM?

    It writes the contents of all tapes one after another, separated by #\## , and marks each head position with a barred symbol such as 0‾,1‾,□‾\overline{0}, \overline{1}, \overline{\square}0,1,□ . So the single tape holds one virtual tape per tape of the multitape TM.Example: tapes 0 1 00\,1\,0010 (head on the second cell) and 1 11\,111 (head on the first cell) become 0 1‾ 0 # 1‾ 10\, \overline{1}\, 0\, \#\, \overline{1}\, 1010#11 .

  8. [Variants of Turing Machines] A 3-tape TM is in this configuration (arrows show the heads): Write it on a single tape, with #\## as separator and barred symbols for the head positions.

    0 1 0 1‾ 0 # 1‾ 1 1 # 0 0 □‾\boldsymbol{0\, 1\, 0\, \overline{1}\, 0\, \#\, \overline{1}\, 1\, 1\, \#\, 0\, 0\, \overline{\square}}01010#111#00□ The third head is on a blank cell, so that blank gets a bar.

  9. [Variants of Turing Machines] Are a multitape TM and a single-tape TM equivalent in efficiency?

    No. They are equivalent in computational power, not in the number of steps. Example: for anbncndna^nb^nc^nd^nanbncndn , a 4-tape TM copies the input on all tapes, and each head checks a separate symbol, instead of one head going back and forth.

  10. [Variants of Turing Machines] What is a TM with a two-dimensional tape, and is it more powerful than a standard TM?

    A TM that uses the whole plane as memory. Not more powerful: an ordinary TM can simulate it. The head moves one cell left, right, up or down. The plane is equivalent to infinitely many tapes.

  11. [Variants of Turing Machines] How does a 3-tape TM simulate a TM with a two-dimensional tape?

    Tape 1 holds the symbols, tape 2 their xxx -coordinates, tape 3 their yyy -coordinates. Numbers can be written in unary (3 as 111111111 ), with another special symbol for the minus sign. A 3-tape TM can in turn be simulated with a single tape.

  12. [Variants of Turing Machines] Why is a 3-tape TM simulating a two-dimensional tape (tapes: symbols, xxx -coordinates, yyy -coordinates) slower than the two-dimensional TM?

    To find a neighboring cell, it must search the whole tape for the right coordinates; the two-dimensional TM moves one unit left, right, up or down. The languages recognized are still the same.

  13. [Variants of Turing Machines] What is a nondeterministic Turing machine?

    A TM whose computation branches at each nondeterministic choice, so it may have two or more outputs for the same input. One can think of many machines working in parallel, each branching creating new machines: It accepts if some branch of this tree accepts.

  14. [Variants of Turing Machines] How does a deterministic TM simulate a nondeterministic TM?

    It searches the tree of computations and halts with accept when it finds an accepting branch. For each branch it stores the tape contents, the state and the head position, copying all of them at each branching. A 3-tape TM can do this, and so can a single-tape TM.

  15. [Variants of Turing Machines] A deterministic TM simulates a nondeterministic TM by searching its tree of computations for an accepting branch. Why must the search be breadth-first, not depth-first?

    Depth-first search may follow an infinitely long branch and never reach an accepting branch that exists. Example: branch 1 never halts, branch 2 accepts after 3 steps. Depth-first search stays in branch 1 forever; breadth-first search reaches the accept in branch 2 at depth 3.

  16. [Universal Turing Machine] How does the book encode a DFA as a string?

    For each state: #\## , the state, AAA (accept state) or RRR (not), then for each input symbol, the symbol followed by the state it leads to.

  17. [Universal Turing Machine] A DFA is encoded state by state: #\## , the state, AAA (accept state) or RRR (not), then for each input symbol the symbol and the state it leads to. State q1q_1q1​ of this DFA is encoded as #q1Raq3bq2\#q_1Raq_3bq_2#q1​Raq3​bq2​ . Encode states q2q_2q2​ and q3q_3q3​ .

    #q2Raq3bq2#q3Aaq2bq2\boldsymbol{\#q_2Raq_3bq_2\#q_3Aaq_2bq_2}#q2​Raq3​bq2​#q3​Aaq2​bq2​ q2q_2q2​ : not accepting, a→q3a \to q_3a→q3​ , b→q2b \to q_2b→q2​ . q3\ q_3 q3​ : accepting, a→q2a \to q_2a→q2​ , b→q2b \to q_2b→q2​ .

  18. [Universal Turing Machine] How can a string like #q1Raq3bq2\#q_1Raq_3bq_2#q1​Raq3​bq2​ (an encoded DFA state) be written with only 0s and 1s?

    Number the states as 1,11,111,…1, 11, 111, \dots1,11,111,… , use 000 as a cell separator, 000000 for #\## , and give a special number to each symbol like A,R,a,bA, R, a, bA,R,a,b . Example: #q1Raq3bq2→00101010111011011\#q_1Raq_3bq_2 \to 00101010111011011#q1​Raq3​bq2​→00101010111011011 .

  19. [Universal Turing Machine] Why can NFAs, PDAs and TMs all be encoded as binary strings?

    They have finitely many states, so each is a finite amount of information. Once a convention is agreed on, that information can be written in 0s and 1s.

  20. [Universal Turing Machine] What is a Universal Turing Machine (UTM)?

    A TM that can simulate any TM, given as a string, on any input. Ordinary TMs are like programs that do one job; a UTM is like a computer that executes any program stored in the form of a TM.

  21. [Universal Turing Machine] What do the 3 tapes of the Universal Turing Machine hold?

    Tape 1: the TM to simulate. Tape 2: the input. Tape 3: the current state of the simulated TM. Based on the description on tape 1, the UTM reads the input on tape 2 and the state on tape 3 and continues the computation.

  22. [Universal Turing Machine] A Universal Turing Machine has 3 tapes. Tape 1: the TM to simulate. Tape 2: the input. Tape 3: the current state of the simulated TM.Which tapes change during the computation, and where is the output at the end?

    Tapes 2 and 3 change, tape 1 is fixed. The output is on tape 2.

  23. [Universal Turing Machine] In the model of computation by a Universal Turing Machine, the UTM is like a computer, the given TM is like a program, and the given string is the data of the program.

    The UTM can simulate any TM, in other words any computer.

  24. [Decidable Languages] What are the three possible results of running a TM on an input?

    ACCEPT, REJECT, or LOOP (the computation continues indefinitely). Looping does not happen for DFAs or PDAs.

  25. [Decidable Languages] This TM starts in q0q_0q0​ with the head on the first input symbol; $\text{\textdollar}$ marks the left end of the tape. What does it do on 111111111111 , on 001100110011 , and on 110011001100 ?

    111111111111 : accepts. 001100110011 : rejects. 110011001100 : loops. 111111111111 : moves right over the 1s, reads □\square□ , accepts. 001100110011 : reads 000 , moves left onto $\text{\textdollar}$ , rejects. 110011001100 : moves right to the first 000 , moves left onto the 111 , moves right onto the 000 , and so on forever.

  26. [Decidable Languages] This TM starts in q0q_0q0​ with the head on the first input symbol; $\text{\textdollar}$ marks the left end of the tape. Which inputs over {0,1}\{0, 1\}{0,1} does it accept, which does it reject, and on which does it loop?

    Accepts 1∗1^*1∗ , rejects strings starting with 000 , loops on all other strings containing a 000 . At the first 000 that is not at the start, the head moves left onto a 111 , then right onto the same 000 , forever.Example: ε\varepsilonε and 111111 are accepted, 010101 is rejected, 101010 loops.

  27. [Decidable Languages] What is a decider?

    A Turing machine that halts on all inputs. So it always ends in qacceptq_{\text{accept}}qaccept​ or qrejectq_{\text{reject}}qreject​ , after finitely many steps.

  28. [Decidable Languages] When is a language LLL Turing-decidable?

    When there is a TM for LLL that is a decider (halts on all inputs). Example: {1}∗\{1\}^*{1}∗ is Turing-decidable: a TM that moves right, rejects at a 000 and accepts at the blank □\square□ always halts.

  29. [Decidable Languages] MMM is a TM for a language LLL , and www is an input. What happens for w∈Lw \in Lw∈L and for w∉Lw \notin Lw∈/L , if MMM is a decider for LLL , and if MMM is a recognizer for LLL ?

    Decider w∈L⇒Mw \in L \Rightarrow Mw∈L⇒M ends in qacceptq_{\text{accept}}qaccept​ ; w∉L⇒M\ w \notin L \Rightarrow M w∈/L⇒M ends in qrejectq_{\text{reject}}qreject​ . Recognizer w∈L⇒Mw \in L \Rightarrow Mw∈L⇒M ends in qacceptq_{\text{accept}}qaccept​ ; w∉L⇒M\ w \notin L \Rightarrow M w∈/L⇒M ends in qrejectq_{\text{reject}}qreject​ or MMM loops. Example: the TM that moves right over 1s, accepts at the blank, and at a 000 moves left (rejecting if at the start) recognizes 1∗1^*1∗ but loops on 101010…

  30. [Decidable Languages] A recognizer for LLL (a TM that accepts exactly the strings in LLL , but may loop on strings not in LLL ) has been running on www for a very long time. What is the problem?

    One cannot tell whether it will accept if one waits long enough, or whether it loops.

  31. [Decidable Languages] How are the Turing-recognizable and the Turing-decidable languages related?

    Every Turing-decidable language is Turing-recognizable. A decider for LLL is in particular a recognizer for LLL .

  32. [Decidable Languages] Turing-recognizable languages are also called recursively enumerable; Turing-decidable languages are also called recursive.

  33. [Decidable Languages] What are the three levels of describing a Turing machine?

    Low-level A state diagram, similar to those of PDAs. Example: q0undefined1→1,Rq0q_0 \xrightarrow{1 \to 1, R} q_0q0​1→1,R​q0​ , q0undefined□→□,Rqaccept\ q_0 \xrightarrow{\square \to \square, R} q_{\text{accept}} q0​□→□,R​qaccept​ Medium-level Pseudo-code. Example: "If input is 111 : move head right, go to 1. If input is □\square□ : ACCEPT." High-level A description of the algorithm in words. Example: "Use DFS to detect cycles. If there is a cycle, REJECT." The lower the level, the more complicat…

  34. [Decidable Languages] Two computer programs, seen as black boxes, take a page of nnn characters from an alphabet of kkk characters as input and output another page. A TM gives them inputs and ACCEPTs if they always return the same output for the same input, REJECTs otherwise.Is this TM a decider?

    Yes. There are finitely many inputs, kn\boldsymbol{k^n}kn , and the TM can check all of them and then halt. It may REJECT much earlier, at the first input with different outputs.Example: k=2k = 2k=2 , n=3n = 3n=3 : 23=82^3 = 823=8 inputs to check.

  35. [Decidable Languages] Is the language of all strings that represent trees (connected undirected graphs without cycles) decidable?

    Yes. A decider: use DFS or BFS from any vertex; if a vertex is unreached, REJECT. Use DFS or BFS to detect cycles; if there is a cycle, REJECT, else ACCEPT. The left graph can be represented by the string A00D 000B00C0D 000C00B 000D00A0B0E 000E00DA00D\,000B00C0D\,000C00B\,000D00A0B0E\,000E00DA00D000B00C0D000C00B000D00A0B0E000E00D (each vertex followed by its neighbors).

  36. [Acceptance and Emptiness Problems] What does ⟨O⟩\langle O \rangle⟨O⟩ denote?

    The string representation of the object OOO . Example: ⟨D⟩\langle D \rangle⟨D⟩ is a string encoding the DFA DDD ; ⟨D,w⟩\langle D, w \rangle⟨D,w⟩ encodes the DFA DDD together with the string www .

  37. [Acceptance and Emptiness Problems] What is the language ADFAA_{\mathsf{DFA}}ADFA​ ?

    ADFA={⟨D,w⟩∣D is a DFA that accepts the string w}\boldsymbol{A_{\mathsf{DFA}} = \{\langle D, w \rangle \mid D \text{ is a DFA that accepts the string } w\}}ADFA​={⟨D,w⟩∣D is a DFA that accepts the string w} Deciding ADFAA_{\mathsf{DFA}}ADFA​ means: given a DFA DDD and a string www , determine in finite time whether DDD accepts www .

  38. [Acceptance and Emptiness Problems] ADFA={⟨D,w⟩∣D is a DFA that accepts the string w}A_{\mathsf{DFA}} = \{\langle D, w \rangle \mid D \text{ is a DFA that accepts the string } w\}ADFA​={⟨D,w⟩∣D is a DFA that accepts the string w} Is ADFAA_{\mathsf{DFA}}ADFA​ decidable? How?

    Yes. Simulate DDD on www ; when the input ends, ACCEPT if the current state is an accept state, else REJECT. The TM stores the description of DDD , the string www , the position on the input and the current state. Each step reads one input symbol, so the simulation never loops.

  39. [Acceptance and Emptiness Problems] What is the language ACFGA_{\mathsf{CFG}}ACFG​ ?

    ACFG={⟨G,w⟩∣G is a CFG that generates the string w}\boldsymbol{A_{\mathsf{CFG}} = \{\langle G, w \rangle \mid G \text{ is a CFG that generates the string } w\}}ACFG​={⟨G,w⟩∣G is a CFG that generates the string w}

  40. [Acceptance and Emptiness Problems] ACFG={⟨G,w⟩∣G is a CFG that generates the string w}A_{\mathsf{CFG}} = \{\langle G, w \rangle \mid G \text{ is a CFG that generates the string } w\}ACFG​={⟨G,w⟩∣G is a CFG that generates the string w} Why does "generate all strings of GGG one by one and compare each to www " not show that ACFGA_{\mathsf{CFG}}ACFG​ is decidable?

    If L(G)L(G)L(G) is infinite and w∉L(G)w \notin L(G)w∈/L(G) , this never halts. It is like searching for a node in an infinite tree using DFS.

  41. [Acceptance and Emptiness Problems] ACFG={⟨G,w⟩∣G is a CFG that generates the string w}A_{\mathsf{CFG}} = \{\langle G, w \rangle \mid G \text{ is a CFG that generates the string } w\}ACFG​={⟨G,w⟩∣G is a CFG that generates the string w} How does a TM decide ACFGA_{\mathsf{CFG}}ACFG​ ?

    Convert GGG to Chomsky normal form. With n=∣w∣≥1n = |w| \ge 1n=∣w∣≥1 , check all derivations with exactly 2n−12n - 12n−1 steps; ACCEPT if one gives www , else REJECT. If w=εw = \varepsilonw=ε , check all derivations with 1 step instead. There are finitely many derivations of a given length, so the TM always halts.

  42. [Acceptance and Emptiness Problems] GGG is a grammar in Chomsky normal form and www a string with ∣w∣=n≥1|w| = n \ge 1∣w∣=n≥1 . Why does every derivation of www from GGG have exactly 2n−12n - 12n−1 steps?

    n−1n - 1n−1 steps with rules A→BCA \to BCA→BC produce nnn variables, and nnn steps with rules A→aA \to aA→a turn them into terminals. Each rule A→BCA \to BCA→BC adds one variable; each rule A→aA \to aA→a replaces one variable by one terminal.Example: S→ABS \to ABS→AB , A→aA \to aA→a , B→bB \to bB→b : S⇒AB⇒aB⇒abS \Rightarrow AB \Rightarrow aB \Rightarrow abS⇒AB⇒aB⇒ab , 3=2⋅2−13 = 2 \cdot 2 - 13=2⋅2−1 steps.

  43. [Acceptance and Emptiness Problems] Is it decidable whether an NFA, a regular expression or a PDA accepts (generates) a given string www ?

    Yes. Convert the NFA or regular expression to an equivalent DFA, and the PDA to an equivalent CFG, then decide as for DFAs and CFGs. Example: an NFA NNN and www : build the DFA DDD with the subset construction, then simulate DDD on www .

  44. [Acceptance and Emptiness Problems] What is the language EDFAE_{\mathsf{DFA}}EDFA​ ?

    EDFA={⟨D⟩∣D is a DFA and L(D)=∅}\boldsymbol{E_{\mathsf{DFA}} = \{\langle D \rangle \mid D \text{ is a DFA and } L(D) = \varnothing\}}EDFA​={⟨D⟩∣D is a DFA and L(D)=∅} Deciding it means: given a DFA DDD , determine in finite time whether DDD accepts any string.

  45. [Acceptance and Emptiness Problems] EDFA={⟨D⟩∣D is a DFA and L(D)=∅}E_{\mathsf{DFA}} = \{\langle D \rangle \mid D \text{ is a DFA and } L(D) = \varnothing\}EDFA​={⟨D⟩∣D is a DFA and L(D)=∅} How does a TM decide EDFAE_{\mathsf{DFA}}EDFA​ ?

    Mark all states reachable from the start state; if a marked state is an accept state, REJECT, else ACCEPT. Marking: mark the start state, then repeatedly mark every state reached by a transition from a marked state, until no new state gets marked. There are finitely many states, so the marking stops.Example: states q1q_1q1​ (start) and q2q_2q2​ (accept), every transition of q1q_1q1​ leads to q1q_1q1​ : only q1q_1q1​ gets marked, so ACCEPT ( L(D)=∅L(D) = \varnothingL(D)=∅ ).

  46. [Acceptance and Emptiness Problems] What is the language ECFGE_{\mathsf{CFG}}ECFG​ ?

    ECFG={⟨G⟩∣G is a CFG and L(G)=∅}\boldsymbol{E_{\mathsf{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG and } L(G) = \varnothing\}}ECFG​={⟨G⟩∣G is a CFG and L(G)=∅} Deciding it means: given a CFG GGG , determine in finite time whether GGG generates any string.

  47. [Acceptance and Emptiness Problems] ECFG={⟨G⟩∣G is a CFG and L(G)=∅}E_{\mathsf{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG and } L(G) = \varnothing\}ECFG​={⟨G⟩∣G is a CFG and L(G)=∅} How does a TM decide ECFGE_{\mathsf{CFG}}ECFG​ , with GGG in Chomsky normal form and start variable SSS ?

    Mark every AAA with a rule A→aA \to aA→a ; repeatedly mark AAA for a rule A→BCA \to BCA→BC with B,CB, CB,C marked, until nothing changes. If SSS is not marked, ACCEPT, else REJECT. A variable gets marked exactly when it generates some string of terminals. This builds a path from the terminals to the start variable.Example: S→ABS \to ABS→AB , A→aA \to aA→a , B→BBB \to BBB→BB : AAA is marked, BBB and SSS never are, so ACCEPT ( L(G)=∅L(G) = \varnothingL(G)=∅ ).

  48. [Acceptance and Emptiness Problems] L={⟨D,k⟩∣D is a DFA that rejects all strings w with ∣w∣≤k}L = \{\langle D, k \rangle \mid D \text{ is a DFA that rejects all strings } w \text{ with } |w| \le k\}L={⟨D,k⟩∣D is a DFA that rejects all strings w with ∣w∣≤k} Is LLL decidable? How?

    Yes. Mark the start state, then kkk times mark the states reachable in one step from marked states. If an accept state ever gets marked, REJECT, else ACCEPT. After iii rounds, the marked states are those reachable by strings of length at most iii . The start state counts too: if it is an accept state, DDD accepts ε\varepsilonε , so REJECT.Another decider: list all strings of length ≤k\le k≤k , simulate DDD on each, REJECT if one is accepted. It needs more steps but still works.

  49. [Acceptance and Emptiness Problems] What are the languages ATMA_{\mathsf{TM}}ATM​ and ETME_{\mathsf{TM}}ETM​ ?

    ATM={⟨M,w⟩∣M is a TM that accepts w}\boldsymbol{A_{\mathsf{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM that accepts } w\}}ATM​={⟨M,w⟩∣M is a TM that accepts w} , ETM={⟨M⟩∣M is a TM and L(M)=∅}\ \boldsymbol{E_{\mathsf{TM}} = \{\langle M \rangle \mid M \text{ is a TM and } L(M) = \varnothing\}} ETM​={⟨M⟩∣M is a TM and L(M)=∅}

  50. [Acceptance and Emptiness Problems] ATM={⟨M,w⟩∣M is a TM that accepts w}A_{\mathsf{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM that accepts } w\}ATM​={⟨M,w⟩∣M is a TM that accepts w} . A Universal Turing Machine can simulate any TM MMM on any string www .Why doesn't simulating MMM on www with the UTM show that ATMA_{\mathsf{TM}}ATM​ is decidable, as simulation does for ADFAA_{\mathsf{DFA}}ADFA​ ?

    MMM may loop on www , and then the simulation never ends. Unlike DFAs and PDAs, TMs can enter infinite loops. The simulation gives a recognizer for ATMA_{\mathsf{TM}}ATM​ , not a decider. All languages before ATMA_{\mathsf{TM}}ATM​ and ETME_{\mathsf{TM}}ETM​ in the book are Turing-decidable.

  51. [Exercises] A TM cannot modify any symbol it has written on its tape (the tape is infinite but write-once). Is it equivalent to a standard TM?

    Yes. At each step it copies all contents of the tape to fresh cells, with the single cell modified. Very inefficient, but it works.

  52. [Exercises] Is a PDA with two stacks equivalent to a standard TM?

    Yes. Each stack holds one part of the TM's tape; moving the head means moving a symbol from one stack to the other. Start by putting the whole tape in one stack and leaving the other empty.

  53. [Exercises] A TM MMM recognizes a language LLL and loops on some strings that are not in LLL . Can we conclude that LLL is not decidable?

    No. LLL is undecidable only if every TM that recognizes LLL loops on some string. Example: a TM that moves right over 1s, accepts at the blank, and at a 000 moves left (rejecting if at the start) recognizes 1∗1^*1∗ and loops on 101010 ; yet 1∗1^*1∗ is decidable.

  54. [Exercises] Is the language of binary representations of prime numbers decidable?

    Yes. An algorithm that tests whether a number is prime always halts, and it can be expressed as a TM. Example: 101∈L101 \in L101∈L (5), 110∉L110 \notin L110∈/L (6), 111∈L111 \in L111∈L (7).

  55. [Exercises] A state of a DFA is redundant if it is not reachable from the start state. Is the language of all DFAs without redundant states decidable?

    Yes. Mark the start state, repeatedly mark all states reachable from marked states until no new state is marked; REJECT if some state is unmarked, else ACCEPT.

  56. [Exercises] Is the complement L‾\overline{L}L of a decidable language LLL decidable?

    Yes. Swap the ACCEPT and REJECT states of a TM that decides LLL . This works because the decider halts on every input.

  57. [Exercises] L1L_1L1​ and L2L_2L2​ are decidable. Are L1∪L2L_1 \cup L_2L1​∪L2​ and L1∩L2L_1 \cap L_2L1​∩L2​ decidable?

    Yes, both. Run the deciders for L1L_1L1​ and L2L_2L2​ as subroutines and combine their results with OR (union) or AND (intersection). Both deciders halt, so the combined TM halts.

  58. [Exercises] L1L_1L1​ and L2L_2L2​ are decidable. Is the concatenation L1∘L2L_1 \circ L_2L1​∘L2​ decidable?

    Yes. Divide the input www into two parts w=xyw = xyw=xy at every possible point; ACCEPT if for some division x∈L1x \in L_1x∈L1​ and y∈L2y \in L_2y∈L2​ , else REJECT. There are ∣w∣+1|w| + 1∣w∣+1 divisions and each test halts, so the TM never loops.Example: w=abw = abw=ab is divided as (ε,ab)(\varepsilon, ab)(ε,ab) , (a,b)(a, b)(a,b) , (ab,ε)(ab, \varepsilon)(ab,ε) .

  59. [Exercises] LLL is decidable. Is L∗L^*L∗ decidable?

    Yes. ACCEPT ε\varepsilonε ; for w≠εw \ne \varepsilonw=ε , try every division of www into nonempty parts and ACCEPT if for some division all parts are in LLL , else REJECT. A string of length n≥1n \ge 1n≥1 has 2n−12^{n-1}2n−1 divisions into nonempty parts, finitely many.Example: w=aabw = aabw=aab has the 22=42^2 = 422=4 divisions aabaabaab , a∣aba \mid aba∣ab , aa∣baa \mid baa∣b , a∣a∣ba \mid a \mid ba∣a∣b .

  60. [Exercises] Is the complement of a Turing-recognizable language always Turing-recognizable?

    No. A recognizer for LLL may loop on a string s∉Ls \notin Ls∈/L , so it cannot be used to accept s∈L‾s \in \overline{L}s∈L . Example: ATMA_{\mathsf{TM}}ATM​ is Turing-recognizable, but its complement is not.