1
$\begingroup$

I want to know how I can calculate/find out which SPACE a language has, because I don't get it. I have this definition

Definition: Fix a function $f: \mathbb N → \mathbb N$. We say that a language $A$ is contained in $\text{SPACE}(f(n))$ if there is a Turing Machine (TM) that decides $x\in A$ vs $x\not\in A$ based on a maximum number of const $\times f(|x|)$ non-blank tape symbols. In the following, mark the strongest assertion that is still true.

I have this question and 4 possible assertions (the same assertion can be selected multiple times).

  1. Let $A\subseteq\{0,1\}^*$ be a regular language. i.e. a lanugage that can be decided by a finite state automaton. Then $A\in$

The assertions are:
$\quad$(a) $A\in\text{SPACE}(\log(n))$;
$\quad$(b) $A\in\text{SPACE}(n)$;
$\quad$(c) $A\in\text{SPACE}(n^2)$;
$\quad$(d) $A\in\text{SPACE}(2^n).$

$\endgroup$
3
  • $\begingroup$ If a language is regular, then you can decide it with a Turing machine that uses no space. You may think of finite automata as Turing machines with no tape if that helps you. $\endgroup$
    – Ordoshsen
    Jan 11, 2022 at 23:17
  • $\begingroup$ @Ordoshsen but there should be one of this answers correct. (All of them are correct but, I thought one of them should really be the strongest assertion and not only the strongest assertion of all answers) $\endgroup$
    – OttoFran
    Jan 12, 2022 at 21:48
  • $\begingroup$ Are you sure the assignment (or wherever the question popped up) asked about regular languages? If so the strongest answer here is space(log(n)), the strongest assertion is space(1) (or even space(0) if something like that makes sense). Another possibility is whoever assigned this tried to be cheeky and if they use a single-tape TM where the input is considered as used by the TM then maybe they want you to answer space(n). But in that case e.g. class L wouldn't make sense so this depends on the concrete TM definition. $\endgroup$
    – Ordoshsen
    Jan 12, 2022 at 22:18

2 Answers 2

1
$\begingroup$

As stated by Ordoshsen, if $A$ is a regular language, then: $$A \in \mathsf{SPACE}(1)\subset \mathsf{SPACE}(\log n)\subset\mathsf{SPACE}(n)\subset \mathsf{SPACE}(n^2)\subset \mathsf{SPACE}(2^n)$$ so all answers a, b, c and d are true.

To prove that $A \in \mathsf{SPACE}(1)$, consider a DFA $D = (Q, \delta, q_0, F)$ such that $A = L(D)$. Consider a two-tapes Turing machine $(Q\cup\{q_a, q_r\}, \Gamma, \#, q_0, \Delta, q_a, q_r)$ where:

  • $\Gamma = \Sigma\cup\{\#\}$;
  • $q_a\in Q$ is the accepting state, $q_r\in Q$ is the rejecting state;
  • $\Delta$ is defined as follow:
    • for $q\in Q\setminus\{q_a, q_r\}$ and $a \in \Sigma$, $\Delta(q, a) = (\delta(q,a), a, \rightarrow)$;
    • for $q\in Q\setminus\{q_a, q_r\}$, $\Delta(q, \#) = \left\{\begin{array}{rl} (q_a, \#, \rightarrow) & \text{ if }q\in F\\ (q_r, \#, \rightarrow) & \text{ if }q\notin F\end{array}\right.$

So the Turing machine read the input word and makes transitions the same way as the DFA, and accept if the state is final when reaching the end of the word, reject otherwise.

This Turing machine use constant space in the size of the input: here, the considered space is the second tape of the machine, which is never used. The input (or the first tape) is not considered in the running space of the machine.

$\endgroup$
0
$\begingroup$

The space complexity is defined for TMs.

You have to come up with an algorithm (Turing machine) that uses as little space as possible and calculate its space complexity.

$\endgroup$
3
  • $\begingroup$ The space used is usually defined as the largest index the TM tries to access on the tape. $\endgroup$
    – nir shahar
    Jan 11, 2022 at 17:20
  • $\begingroup$ You have to construct a turing machine, not a finite state automaton (even though it is easy to construct a TM from one). The space is measured with relation to the working tape, i.e. the tape you can read and write to (and not the input tape) $\endgroup$
    – nir shahar
    Jan 11, 2022 at 18:18
  • $\begingroup$ What nir shahar said in that last comment is really important. There are two tapes, one read-only with the input on, and one you can read and write to. The space used is the number of cells used on the working tape. $\endgroup$
    – Pål GD
    Jan 11, 2022 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.