2
$\begingroup$

I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?

$\endgroup$
3
  • 3
    $\begingroup$ It’s a language which either contains all strings or contains no strings. $\endgroup$ Jul 3, 2019 at 4:53
  • 2
    $\begingroup$ Did you try Googling this? You seem to ask a lot of very simple questions in a short space of time -- we do expect you to do some basic research on your own before posting here. Remember that every answer people post here takes up some of their time. $\endgroup$ Jul 3, 2019 at 10:24
  • $\begingroup$ @DavidRicherby Yep, I was initially confused by the notion of trivial property and could not find a direct answer. I am also possibly not very good at parsing information haha. I asked here also so that it would be easily accessible for anyone confused in the future. In about a month, I think in hindsight, this question may seem "trivial" $\endgroup$ Jul 3, 2019 at 10:57

1 Answer 1

4
$\begingroup$

A trivial language is one that has no strings, or one that has every string in some alphabet.

In terms of models of computation, a trivial language is one that can be decided by a Turing Machine or lambda function that completely ignores its input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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