1
$\begingroup$

The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general scenerio also. i have taken this argument as my base for the conclusion of my answer as i found this argument somewhere on stackexchanege please correct me if iam wrong.

coming to point , as there are grammar for every language which also indicate existence of set of rules for the formation of the language. Taking this ahead , i wonder if we can device a set of rules which is indeed a process to derive or generate a solution then why cant we form an automata for the same. Adding more to this point , we know the highest class of automata is turing machines capable of accepting many languages but not all , and we know that the languages not accpeted by turing machines have grammars( as said every language has grammar) means there are some machines automata that does not necessarily satisfies the all the langugaes not accepted by turing machines but do satisfy some but all of them , using this we say there are different classes of machines which are not turing but accept some languages not accpeted by turing machines if this is not true than there must exist the languages that do not have any grammar but as said every languae has grammar. adding more woes to this argument , we have not able to identify any machine more powerful then turing , so this means some of the arguments made here are wrong . but i am finding it difficult to understand which one of them is wrong, so please let me know.

Improve this question
$\endgroup$
1
  • $\begingroup$ Both of the answers so far speak to your post. (1) There are many languages that do not have grammars, since (2) there are countably possible grammars, but there are uncountably many possible languages. I presume you know that infinity comes in more than one size; if not, ask for an explanation. $\endgroup$ – Rick Decker Oct 23 '18 at 17:51
2
$\begingroup$

Suppose that $\mathcal{M}$ is any kind of machine model in which every machine has a finite description, say as a binary string. The model can be more powerful than mere Turing machines – for example, it could be Turing machines with access to an oracle for the halting problem.

Since every machine has a finite description as a binary string, there are only countably many machines, and so countably many languages they accept. Since there are uncountably many languages, there must be some language not accepted by any $\mathcal{M}$-machine. In fact, most languages aren't, in the sense that a random language would not be accepted by any $\mathcal{M}$-machine.

The only way out is if machines do not have a finite description. But this is not what we usually understand by machine. An example of such a "machine" is one in which an arbitrary language is hardwired. Such machines can, by definition, accept all languages, but they are not so interesting mathematically.

Improve this answer
$\endgroup$
4
  • $\begingroup$ so in short we have machines for all languages sames as grammar for all languages but we are concerned over machines that are capable of accepting more than one language (in simple terms machines that can do multitask ) and that is the reason we study different model of machines or automata. but the validity of this argument also give rise to another argument the languages like tasks could govern that we could find a machine for all the problem ( languages) but since we have not find solution to some languges , what does that mean? ,is it our inefficiency or its the invalidity of argument? . $\endgroup$ – rballiwal Oct 23 '18 at 7:18
  • $\begingroup$ No, you missed the point entirely. Hopefully someone else will write a better answer. $\endgroup$ – Yuval Filmus Oct 23 '18 at 7:19
  • $\begingroup$ could you give me a hint , will work fine for me $\endgroup$ – rballiwal Oct 23 '18 at 7:20
  • $\begingroup$ if you could break down it step by step then it will be easy to swallow $\endgroup$ – rballiwal Oct 23 '18 at 7:21
2
$\begingroup$

The first premise is wrong. A language over an alphabet is just any subset of all strings made from characters of that alphabet. There are uncountably many languages over any alphabet with two or more letters, there are only countably many grammars. So most languages don't have a grammar at all.

Many of these languages are not useful, but they are still languages.

Improve this answer
$\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.