CODEWITHSUNDEEP
computer-scienceregular-languagecomputation-theoryturing-machinesdecidable
DingDong
DingDong

Reputation: 367

what does regular, Turing-decidable and Turing-recognisable mean?

I know this question has been asked earlier, but I honestly don't understand it clearly.

I'm currently undergoing a study about the theory of computation and I'm coming to the terms "Prove that a language is decidable, recognizable or regular".

In simplest term what do they actually mean, and how do we prove such things?

Upvotes: 2

Views: 3963

Answers (1)

Joshua Gleitze
Joshua Gleitze

Reputation: 927

We are talking about a language L over an Alphabet Sigma, which means that L is a subset of Sigma* (L consists of words that consist of letters from Sigma).

L being decidable
means that there exists a Turing machine T, such that T will halt and accept for any input word omega in L and halt and reject for any input word omega not in L.

L being recognisable
means that there exists a Turing machine T, such that T will halt and accept for any input word omega in L and halt or not halt (but not halt and accept!) for any input omega not in L.

see also Recognizable vs Decidable on MathExchange for the difference.

L being regular
means that L can be created by regular expressions. It is important to note that these regular expressions in theoretical computer science are different from the RegEx features known in Programming Languages like PERL or Java. In fact, these RegExes are truly more powerful (don’t known if that’s the correct english term) than regular expressions.

A good definition of regular expressions is given here:

For an alphabet Sigma

  • the empty set and epsilon (the empty set and the empty word) is a regular expression
  • a for any a in Sigma (any letter from the alpabet) is a regular expression
  • if R1 and R2 are regular expressions, these are regular expressions, too:
    • R1 and R2 (meaning R1 or R2)
    • R1 concatenated with R2 (meaning the concatenation of R1 and R2)
    • R1* (meaning R1, any number of repetitions of R1 or the empty word epsilon)

and nothing else is a regular expression.

How do we proof something like that?

Turing machines

To prove decidability or recognisability, it’s often easiest to provide a Turing machine with the desired attributes. Because of the Church-Turing thesis, any programming language is as powerful as a Turing machine. So in my courses, it was perfectly acceptable to provide an algorithm in a programming language or pseudo code.

Note that any language that is recognisable is also decidable (but not the other way around).

Regular Expressions

To prove regularity, it’s most of the time easiest to just provide a regular expression that constructs the language. Sometimes a prove is needed that the regular expression really constructs exactly L, which is usually not too difficult (often it’s plain obvious).

In many lectures, there is a convention on regular expressions that allows a more intuitive and shorter (but not more powerful) syntax.

It may be interesting to know that regular languages are exactly the languages that can be recognised by finite automatons. Note that any regular language is also decidable (and thus recognisable).

To disprove regularity, I’m just going to mention the pumping lemma for regular languages.

Upvotes: 3

Related Questions