3
$\begingroup$

I am curious about following question. I've read other threads but the problem is slightly different: Is the set of real numbers a language?

So my question is:

If I have a grammar, as defined in https://en.wikipedia.org/wiki/Formal_grammar#The_syntax_of_grammars

  • G = (P,N,S,$\sum$)

    • P-production rules
    • N-non terminals

    • S- StartSymbol-

    • $\sum$ -terminal symbols

is it possible to have the set of real numbers in the set of terminal symbols? The definition of a grammar on wikipedia says no.

Is it possible to define it otherwise?

Improve this question
$\endgroup$
10
  • $\begingroup$ Welcome to SE computer Science. There are probably exceptions for some abstract developments, but you should consider as a general rule that formal devices used to define languages and computation in general are finitely defined. Hence they do not use infinite sets such as the real numbers, or even the integer numbers. What is it that you want to define? What do you want to define it from? $\endgroup$
    – babou
    Commented Oct 29, 2019 at 18:44
  • $\begingroup$ @babou, in formal languages and automata, the infinite is on equal footing with the finite. In regex, for example, we use the symbols, * and + to represent the intervals [0,infinity] and [1,infinity], resp. In fact all grammars and automata (they are isomorphic) are capable of infinite processes. Not only do automata admit working with infinite sequences, but also non-deterministic ones too. In fact, in the study of class equivalences of models of computation, one can also field not just the infinite, but the seminfinite. en.wikipedia.org/wiki/Automata_theory $\endgroup$
    – J D
    Commented Oct 29, 2019 at 20:50
  • $\begingroup$ @J.D.: infinite and unlimited mean different things. Automata (as normally defined, not $\omega$ automata) are not capable of infinite computations. There is no limit to the number of steps, but every process which terminates do so after some finite number of steps. $\endgroup$
    – rici
    Commented Oct 29, 2019 at 21:11
  • $\begingroup$ @JD You seem to confuse syntax and semantics. The finiteness I refer to is the syntactic finiteness of the description of grammars, automata, and other computational devices. This description might sometimes denote infinite entities semantically, but the computation is always performed on syntactic representation. Ignoring ω automata and languages, all you ever deal with is finite. You start with finite input and finite devices, and you perform only finite computation step, so that after a finite time you still have only finite structures.No limitation in size, but nothing becomes infinite. $\endgroup$
    – babou
    Commented Oct 29, 2019 at 22:28
  • $\begingroup$ You said "a general rule that formal devices used to define languages and computation in general are finitely defined". You've already conceded that alphabets can be infinite. From the WP article " An alphabet may contain an infinite number of elements;[3] however, most definitions in formal language theory specify alphabets with a finite number of elements, and most results apply only to them.". $\endgroup$
    – J D
    Commented Oct 29, 2019 at 22:35

2 Answers 2

Reset to default
3
$\begingroup$

You could use the digits $\{0,\dots,9\} =: \Sigma$ as alphabet and consider infinite words. A word corresponds then to a real number. Those are known as $\omega$ languages link. There are omega-regular languages too.

Edit: The set of all real numbers, $\Sigma^\omega$, forms an $\omega$-regular language of course.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Considering infinite words on the digits 0..9 alphabet is indeed one possibility. Omega-regularity seems out of topic. Besides you assertion that real numbers (as infinite strings of digits) do not form an omega-regular language is false. It is trivially omega-regular. Your remark on the incomputability of some reals is irrelevant. $\endgroup$
    – babou
    Commented Oct 29, 2019 at 18:58
  • $\begingroup$ In your edited answer you now assert that -1- real numbers do not form an omega-regular language, and -2- the set of real numbers would be 2ω which is of course Omega regular. Isn't this a bit of a contradiction? Actually (AFAIK, not being a specialist of ω languages) both assertions are wrong. The reals (in binary notation) do form an ω-regular language, but it is not $2^\omega$, where $2$={0,1}. $\endgroup$
    – babou
    Commented Oct 31, 2019 at 11:46
  • $\begingroup$ @babou Sorry for the confusion. I botched the edit. It should be fixed now. The set of all real numbers form of course an omega-regular language and it should be $\Sigma^\omega$ for any sensible alphabet (i.e., base) you like. $\endgroup$
    – Daniel
    Commented Oct 31, 2019 at 13:18
  • $\begingroup$ Well, $\Sigma^\omega$ only gives you the reals in [0,1]. This is often all you want, but all reals in usual based notation is slightly more complex. $\endgroup$
    – babou
    Commented Oct 31, 2019 at 14:10
1
$\begingroup$

Why is it not possible to have the set of reals in terminal symbols? Because you'd have to list ALL of them, and there an infinite number of reals. However, we can (and do) build the reals themselves out of finite symbols, so we merely regress to having the reals constructed. Before we consider whether the reals can be expressed as a formal language, remember that reals are a composite of:

  • Integers
  • Rationals
  • Irrationals

and therefore the formal language must accommodate all of these types since each type must be represented for all to be represented. Using regular expressions:

Let D := {0,1,2,3,4,5,6,7,8,9}, d := {1,2,3,4,5,6,7,8,9}

ℤ := 0 | (+|-)dD*
ℚ := 0/(+|-)dD* | (+|-)dD*/(+|-)dD*
𝕁 := (+|-)DD*.D*

Therefore our alphabet is

Σ := {+,-,/,.,0,1,2,3,4,5,6,7,8,9}

This is almost the language, however, note that we cannot have an empty string represent a real number L which in formal language is technically a sentence, so:

Σ+ = Σ* - {λ} (where λ is the empty string)

Which means r ∈ ℝ in set-theoretic notation is the formal languages equivalent of L ∈ Σ+. So Σ+ is the collection of all reals, and therefore by construction exists. From here, we can use Σ+ as a generator of primitives for other grammars where the primitive is merely ℝ. Anywhere the terminal symbol ℝ occurs, we can generate or check if the string of symbols fits the definition of ℝ.

So while we can't technically build a grammar out of actual infinity of reals, we can construct it in a roundabout manner as a potential infinity. This is where mathematics and computer science differ since the Turing machine is only infinite in mathematical theory and not in physical practice.

EDIT

Read the comments below until I update the posting with the results of the back and forth.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Since the integers are included in the rationals, why do you need to add a specific description of integers? Note also that 3..24.2.3//+ ∈ Σ+ , but it does not denote a real number. So Σ+ is apparently not the set of representation of all real numbers. But what is a representation of a real number? Certainly not (+|-)DD*.D* which represent only a subset of rational numbers, thus including no irrational number. Note also that Σ+ = Σ*-{λ}, but this is a minor typo. $\endgroup$
    – babou
    Commented Oct 29, 2019 at 23:26
  • $\begingroup$ Well, this whole article was off the cuff, so I wouldn't bet on my own accuracy, but let me address. Because technically speaking, an integer may occur in rational form or integral form, and each representation would indicate a different string: "4" and "4/1" are semantically equivalent, but syntactically different. Hence, when parsing an expression we need two different rules. In ordinary math practice, we resolve that logical equivalence in our head unconsciously, but computers have to be instructed to do it. $\endgroup$
    – J D
    Commented Oct 29, 2019 at 23:42
  • $\begingroup$ Also, technically speaking, the irrational definition would be indistinguishable from a subclass of rationals, and to determine whether or not the pattern was rational or rational would require an additional form of verification, by table or logical procedure. Non-terminating, non-repeating decimals and non-terminating, repeating decimals would look identical to a computer, and would require an additional process for disambiguation. In a real application, the irrationals would likely be represented in several ways... $\endgroup$
    – J D
    Commented Oct 29, 2019 at 23:48
  • $\begingroup$ An intensional definition might take the non-terminating decimal and compare against the output of a procedure to calculate an irrational, or an additional symbol might be used in the string "\.\.\." if the user is entering input or the system is indicating in the string it has rounded off... $\endgroup$
    – J D
    Commented Oct 29, 2019 at 23:50
  • $\begingroup$ Or an entirely separate grammar might be used to denote irrationals symbolically, as computer algebra systems don't work with decimal representations of irrationals. Pi and e are likely to be stored as tokens, and those might be interfaced programatically with routines to generate or compare them. $\endgroup$
    – J D
    Commented Oct 29, 2019 at 23:52

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.