-1

So, all languages for which if I can decide the set membership problem by means of computer programs, is it possible, or correct to say that all such languages are regular? If not, why?

Ayush Pathak
  • 1
  • How do you define a regular language? How do you define a computer program? – David K Jan 28 '23 at 03:55
  • I've just started learning toc(haven't reached nfa yet), and I am diving into the fundamentals of the given concept, i.e., computation->program->algorithm->mathematical function->graph of function, where my main concern is to decide whether there exists a general algorithm for a given function. So, I'm concerned with the set membership problem of formal language. If there's a way, say computational method where i can write a program(algorithm) to decide its set membership problem, is it possible that the language is regular? By regular, i mean there exists a dfa M for L such that L(M)=L. – Ayush Pathak Jan 28 '23 at 04:05
  • 1
    Regular languages are a very, very small subset of the set of languages whose decision problem can be solved by a program. As a simple example the language of all words of the form $a^nb^n$ is not regular but it is trivial to write a program to recognize its words. You will probably very soon learn how to prove this is not a regular language, and much more. Do not hurry! – Mariano Suárez-Álvarez Jan 28 '23 at 04:07
  • Could you share more details in the post itself? Thanks. – Phil Jan 28 '23 at 04:08
  • You can write a program to detect palindromes but this cannot be done with a finite state machine. The answer is no. – John Douma Jan 28 '23 at 04:08
  • Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. – Community Jan 28 '23 at 04:08
  • (Feel free to ignore the Bot, which is entirely useless, as it usually is.) Do make sure your question is understandable without its title, though. – Mariano Suárez-Álvarez Jan 28 '23 at 04:09

2 Answers2

1

Depends what you mean by a computer program. If you mean a deterministic finite automaton (DFA), then yes.

Kleene's Theorem. A language is regular if and only if it is recognisable by some DFA.

David
  • 82,662
  • 1
    @MarianoSuárez-Álvarez The theorem I stated is "if and only if", so if the OP doesn't mean a DFA (or something equivalent) then the answer is no. – David Jan 28 '23 at 04:10
  • @DavidK the question was asked before the introduction to pumping lemma. Suppose if we can show that there isn't any algo to solve the set membership problem for graph(f) then, we can conclude that there is no algorithm to compute f (correct me if I'm wrong). But, the question is I've decided the SMP using a comp program for a language, so why can't I say that it is regular, or is it that regularity doesn't immediately point to the existence of a general algo to compute it. If i'm missing any concept, or confusing different concepts, please point it out. – Ayush Pathak Jan 28 '23 at 04:41
  • "Computer program" and "algorithm" are somewhat slippery words depending on context. In the context of the theory of computation a typical definition is, "Something that can be implemented by a Turing machine." A Turing machine can be more than a DFA, and you cannot say that a language accepted by a Turing machine is therefore regular. – David K Jan 28 '23 at 04:48
0

The answer to your question is negative. For instance, you can easily write a computer program to check whether an integer is a square. However, the language $\{a^{n^2} \mid n \geqslant 0\}$ is not regular.

J.-E. Pin
  • 40,163