Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

An ambiguous Language is a formal language for which there exists a string that can have more than one meaning (several possible meanings or interpretations). Multiple synthesis structures for a string.

[Question]
Are Roman numbers an example of an ambiguous language?

Because there can be more then one representation for some number such as 1999, which can be written as MDCCCCLXXXXVIIII, MCMXCIX, or MIM.

I am confused. Sometimes I feel not, some time yes!

EDIT
[ANSWER]

Although there can be more than one representation of same magnitude in Roman Number System. That is basically Non-Positional Number System. But its possible to write Unambiguous Grammar for that can generate all possible/valid pattern in Roman Number System.

Here is again a beautiful link that describe symbol table, rule , Grammar for Roman number.

I am not sure about this but some authors says that: "Roman numbers can be recognized by a regular expression, so you don't really need a context-free grammar." and a regular language can't be ambiguous.

share|improve this question
    
Well, there are inherently ambiguous languages, but that is not your problem here. –  Raphael Jan 23 at 18:16
    
@Raphael I know there are And yes set-of-all-possible-roman numbers (even if rule for more then 5000) is unambiguous. –  Grijesh Chauhan Feb 15 at 6:20
    
More-over If we check definition of formal-grammars (or any represent) then set-of-language-symbol can't be infinite. And because formation rule of Roman number doesn't allow repetition of same number more than 3-times consecutively hence Roman-Numbers are finite in real (can't represent arbitrarily large magnitude) And so @reinierpost's answer is correct!! There are other problem with roman numbers formation rule is not readable --then concept of positional number system came(roman numbers are non-positional number system). –  Grijesh Chauhan Feb 15 at 6:26
add comment

migrated from cstheory.stackexchange.com Jan 5 '13 at 7:47

This question came from our site for theoretical computer scientists and researchers in related fields.

5 Answers

A grammar (not a language!) is ambiguous if there is a word with two "essentially different" parses. Roman numerals are unambiguous - given a roman numeral, it has an unambiguous numerical value. The fact that this correspondence is not one-to-one is beside the point.

share|improve this answer
    
This is the way I think :) .. and it should be correct too! –  Grijesh Chauhan Jan 5 '13 at 8:38
7  
This assumes that you call strings such as IXM invalid, and not Roman numerals. (I have seen IIX = 8 used historically, as well as VIII = 8, but I am fairly sure nobody ever used IXM.) –  Peter Shor Jan 5 '13 at 13:38
add comment

You fell into the trap of thinking that formal language theory deals with meaning. It doesn't.

In formal language theory, a context-free language is ambiguous if some context-free grammar generates exactly that language, but no such grammar does so in such a way that each string in the language has only a single parse tree.

The language of Roman numerals isn't completely standard, but I believe all versions have the property of being finite: I don't think 5000 can be represented, let alone a million. Every finite language is unambiguous: it can be generated by a grammar that directly produces each member string from the start symbol.

(UPDATE: Peter Shor's comments make it clear that this wasn't the case: apparently it was quite common to surround numbers with C Ͻ or | | to multiply them by 1000. When this can be applied arbitrarily often, the language is no longer finite; when it can be done in arbitrary ways, it still doesn't become ambiguous when only C Ͻ is used; when | | is used, the interpretation may become ambiguous, but I still don't think the language becomes ambiguous in the formal, syntactic sense.)

share|improve this answer
    
5000 = (V) or MMMMM. –  Peter Shor Jan 6 '13 at 18:21
    
So what is 50000? –  reinierpost Jan 7 '13 at 19:08
    
(L), of course. Actually, the Romans would have written it more like ϹLϽ (with the two Ϲ's symmetric). Enclosing things in parentheses multiplies them by 1000. If you allow multiple parentheses (I'm not sure whether the Romans used this; it certainly seems to have been rare), you can get any number. –  Peter Shor Jan 7 '13 at 19:47
2  
The idea that the Romans, who successfully managed an empire with millions of people in it, couldn't count beyond 5000 is totally absurd. It does seem that the system for representing numbers above 5000 changed during the Roman empire, so the exact notation they used may have depended on the time period. It is also likely that there were times when two or more different notations were used. However, having two or three different notations for 1,000,000 (or do I mean 10^6?) should not cause a problem. –  Peter Shor Jan 9 '13 at 17:41
1  
It's possible to count much higher than one's notation for numbers reaches by mixing in names for numbers ("50 thousand") or units ("3 days, 17 hours, 4 minutes and 6 seconds"). –  reinierpost Jan 10 '13 at 18:12
show 3 more comments

Its not ambiguous.

Note that if you are writing a smaller digit before a larger one, obviously that means you are subtracting. But notice that those digits must be comparable. I would come before V and X only. X would come before L and C only. C before D and M.

Break the number and then combine their roman correspondents.

49 is 40+9. We dont write it as IL. We first convert 40, then 9 so its XLIX.

99 is not IC. Its 90 (XC) + 9 (IX) ie XCIX.

499 is not ID. Its 400 (CD) + 90 (XC) + 9 (IX) ie CDXCIX.

999 is not IM. Its 900 (CM) + 90 (XC) + 9 (IX) ie CMXCIX.

So, according to this

1999 should be MCMXCIX. 1000 (M) + 900 (CM) + 90 (XC) + 9 (IX).

And also MDCCCCLXXXXVIIII is an invalid representation. You can't have 4 consecutive same letters. Instead you convert it.

M*DCCCC*LXXXXVIIII $\rightarrow$ M*CM*LXXXXVIIII

MCM*LXXXX*VIIII $\rightarrow$ MCM*X*VIIII

MCMXC*VIIII* $\rightarrow$ MCMXC*IX*

This online conversion tool might be helpful.

share|improve this answer
    
According to wikipedia, having 4 times the same symbol was actually common, –  babou Feb 14 at 22:56
add comment

You are confusing several concepts of ambiguity, and using your own definition backward.

There is the concept of semantic ambiguity: is it possible to have different meanings for the same string. In your case: is it possible that 2 different numbers are written in the same way in Roman numerals. The answer is clearly no, because there is a simple deterministic algorithm to compute the value represented by a Roman numeral.

However, when you talk of formal language, you are considering only syntactic structures (usually tree structure) associated to string in accordance with the way these strings can be generated by a grammar. Identifying a tree associated with a string is called parsing.

Then there is the concept of syntactic ambiguity. Are there two different ways to parse some numerals into a structure. I cannot answer that since you do not give a formal definition of the structure of roman numerals.

But let us assume that you are only considering structure defined by a context-free (CF) grammar. Then you may wonder whether the Roman numerals can be generated by an unambiguous CF grammar (they can, though I did not check the grammar on the site you discovered). But there are CF languages that will not have an unambigous grammar. Such CF languages are said to be inherently ambiguous.

Does syntactic ambiguity really matter? Not necessarily if you are only interested in the meaning of sentences, here in the integer values represented by Roman numerals. Syntactic structure is normaly used to define semantic, that is, meaning. If the same sentence has two structure because of grammatical ambiguity, that could be a problem. But it could also be that the way meaning is associated with the structure of a sentence (the parse tree) is such that it produces the same meaning for all strucures corresponding to a same sentence. Syntactic ambiguity does not necessarily result in semantic ambiguity.

The Romans numerals can be defined as a formal language, for example with a CF grammar. But you are also associating a meaning with each string, which means that you are considering more than a formal language. Hence you should be clear whether you talk of syntactic ambiguity, or of semantic ambiguity.

Now, you may have two distinct Roman numerals that represent the same number, as you show in your question, and which is confirmed by wikipedia. For example VIIII and IX. That is not ambiguity. It is a very common situation when a given meaning can be expressed syntactically by different strings. While you stated correctly that (semantic) ambiguity is when a string can have more than one meaning.

To take it with natural language, the sentence "John sees a man with a telescope" is ambiguous because you cannot determine whether John is using a telescope, or whether the man is carrying one.

But the fact that both sentences "the dog eats the bone" and "the bone is eaten by the dog" mean the same thing is not a problem for anyone.

From what I read in wikipedia, there is a finite number of Roman numerals. Hence they can be trivially represented by a regular grammar. And a regular grammar is an unambiguous CF grammar. But that is a trivial argument that provides no insight.

What you want is a CF grammar that will identify as a tree the organization of a Roman numeral so that it will be easier to compute its meaning: the associated integer. This is possible in various ways.

share|improve this answer
    
I know a class of ambiguous language exists. I discovered set of Roman Numbers as formal language is not ambiguous. Yes two roman numbers can representation same magnitude but it doesn't makes set-of-all-roman-numbers an ambiguous language. In fact more than one expressions in set-of-math-expressions e.g 2 + 2 + 2 and 3 * 2 represents same magnitude but it is unambiguous The same way- set-of-all-all-possible roman numbers are unambiguous. Thanks for your answer. –  Grijesh Chauhan Feb 15 at 6:18
add comment

The translation from Arabic numbers to Roman numbers is very straight forward and absolute not 'unambiguous'.

You can translate each Arabic digit to exact one Roman representation.

Arabic:    1    2    3    4    5    6    7    8    9
Roman:     I   II  III   IV    V   VI  VII VIII   IX

Arabic:   10   20   30   40   50   60   70   80   90
Roman:     X   XX  XXX   XL    L   LX  LXX LXXX   XC

Arabic:  100  200  300  400  500  600  700  800  900
Roman:     C   CC  CCC   CD    D   DC  DCC DCCC   CM

Arabic: 1000 2000 3000  
Roman:     M   MM  MMM 

Combine a number from the highest to the lowest digit.

E.g.
1999 is (with space) M CM XC IX and together MCMXCIX.

share|improve this answer
5  
This is indeed the modern formula, but it wasn't the only way the Romans did it. At some point, somebody decided that there should only be one Roman number for positive each integer, and come up with this system. MIM would have been perfectly acceptable to the Romans. –  Peter Shor Jan 6 '13 at 18:19
    
@petershor, can you cite some research that demonstrates this assertion? I don't disbelieve you, just want to know what has been done to discover this. –  Nicholas Jan 24 '13 at 11:11
1  
Look in the lower right corner of this picture from the Arch of Augustus. You should see DCXXXIIX. And here is DCCCCXVII from this website. –  Peter Shor Jan 24 '13 at 11:58
    
Also look for 4 in roman numerals on clocks, it is (somewhat) common to see IIII for it (not IV). –  vonbrand Jan 24 at 13:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.