1
$\begingroup$

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ is the real part and $b$ is the imaginary part of the complex number.
Now, Assume that $C$ is the language of complex numbers.

Q1: Is $C$ a regular language?
Q2: Write a regular expression for $C$
Q3: Draw a DFA accepting $C$ if you can.

Note: I'm confused with the symbols. For example i don't know how to show $( \sqrt 2 , i )$ . I mean, $i$ is a non-terminal symbol. Can i have this symbol in my regular expression? The other problem is that i don't know how to show $( \sqrt )$.

$\endgroup$
  • $\begingroup$ Where did this question come from, and are there any further details? In particular, is a language for real numbers given? Remember that most real numbers do not have finite representations... $\endgroup$ – Chris Culter Apr 21 '16 at 8:28
  • 1
    $\begingroup$ @ChrisCulter In the book written by peter linz, there is a question like this for real numbers. I was curious myself about this question :) Is it bad to ask ? $\endgroup$ – Arman Malekzadeh Apr 21 '16 at 9:46
  • $\begingroup$ Well, it's probably a good question, but it needs details to be answered definitively. If we're going by Peter Linz's book "An Introduction to Formal Languages and Automata", it seems that whenever he talks about "real numbers", he specifically means numerical constants in the C programming language. These include "1.23" and "-4" but not "sqrt(2)" or "0.333...". Of course, you're free to mean something different by "real numbers", possibly including "sqrt(2)". It would be good to specify what that language is, in the question. $\endgroup$ – Chris Culter Apr 21 '16 at 10:18
  • $\begingroup$ @ChrisCulter as i wrote in my question, i mean the real real real numbers !!! so sqrt(2) is included :) $\endgroup$ – Arman Malekzadeh Apr 21 '16 at 10:49
  • $\begingroup$ Okay, but then, do you want to represent "sqrt(2)" as a sequence of 7 Latin characters, "s" followed by "q" followed by... Or maybe you want to represent every real number as an atomic symbol in the alphabet of your language? $\endgroup$ – Chris Culter Apr 21 '16 at 18:24
1
$\begingroup$

I can't answer all of your questions, but I can tell you how I would attempt to do it.

a + bi is made from 3 components, real numbers (a, b), operators (+) and the imaginary symbol (i). So we need to be able to express all 3. + and i are easy, it's just the symbol themselves.

So onto a real number, we can either write its decimal expansion (4.2) or with algebraic symbols (sqrt(3)/2). One of these is much simpler, but since you included sqrt, is say you need the latter.

Let's build up and see where we get to. 2 is easy it's just [0-9]. 42? [0-9]+

-7? (-)[0-9]+ sqrt(-7)? Oh, we don't want to be able to show, since that wouldn't be a real number. Sqrt(7)? (-)(sqrt)[0-9]+ sqrt(3)/2? (-)(sqrt)[0-9]+(/[0-9]+) sqrt(3/2)? (-)(sqrt)[0-9]+(/[0-9]+) But they are the same? Oh, we made a mistake, we forgot about parenthesis. From the pumping lemma, we can't describe parenthesis that are matched, so this definition is not a regular language. :/

Fine, lets pick the first way of expressing real numbers. I'm going to gloss over the steps here, since it is a quick google away.

(-)[0-9]+(.[0-9]+) where we escaped the . So that we know it's just a dot and not any single symbol.

Thus we say we can represent a complex number by [(-)[0-9]+(.[0-9]+)([+-][0-9]+(.[0-9]+)i)|[0-9]+(.[0-9]+)i)] Notice the second choice is so we can write 21, or -5i, but we can also write 3i and not be forced into +3i

$\endgroup$
  • $\begingroup$ Please format your post using Mathjax $\endgroup$ – R_D Apr 21 '16 at 8:22
  • $\begingroup$ I'm on mobile, so I can't at the moment $\endgroup$ – James Apr 21 '16 at 8:29

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.