BNF grammar for a palindrome

Question

I need help with a non-extended BNF grammar:

Σ = {a,b}
L = {ω ɛ Σ^* | such that w is equal to the reverse of ω}

For example, the strings aba, bab, and ababa are in the language, but string ababab is not.

I am not sure if this is a solution but this is what I found online and I am wondering if I am heading in the right direction:

<palindrome> ::= a <palindrome> a | b <palindrome> b |
                 c <palindrome> c | d <palindrome> d | 
                 e <palindrome> e | ...
                                  | z <palindrome> z
<palindrome> ::= <letter>
<letter>     ::= a | b | c | ... | y | z

@arkascha it's not homework question. It's one of the practice exam question that i am trying to resolve before i take exam next week. — Jon Abraham, Jun 21 '15 at 06:08
@arkascha is this the answer - ::= a a | b b | c c | d d | e e | ... | z z ::= ::= a | b | c | ... | y | z — Jon Abraham, Jun 21 '15 at 06:09
@arkascha would appreciate even if you can guide me a little bit. The problem here is i am trying to find possible information to solve this question and have no clue on how to resolve this. I posted a possible resolution wondering if you can tell me if that is right ? — Jon Abraham, Jun 21 '15 at 06:11
@arkascha yes w stands for strings and starting should be with left brace { and ending with right brace }. Summation would be sigma — Jon Abraham, Jun 21 '15 at 06:31
Your answer does not seem right... what about non-latin characters? You are trying to create a non countable solution set by iteration. That cannot work. — arkascha, Jun 21 '15 at 06:36
Please also add your proposed solution to the question, so that it get's more readable. Thanks! — arkascha, Jun 21 '15 at 06:38
@arkascha yes i edited necessary part. May i know then what would be right solution then ? — Jon Abraham, Jun 21 '15 at 06:38
It is _not_ a correct solution. Besides what I mentioned above it does not contain words with an even number of characters (example: "abba"). — arkascha, Jun 21 '15 at 06:39
What is the notation of "arbitrary but fixed" in BNF again? (Sorry if the phrase is unknown, I am translating from my native language to Englisch...) — arkascha, Jun 21 '15 at 06:42
No, that is not what I meant. I meant "an arbitrary but fixed character". Typical mathematical expression. Should be the same in formal language theory, shouldn't it? — arkascha, Jun 21 '15 at 06:44
Your example gives you all odd-length palindromes for the alphabet Σ = { a,b,c,...,x,y,z }. You want to restrict it to just the alphabet Σ = {a,b}, and add in something to match even length palindromes... — Chris Dodd, Jun 21 '15 at 07:15

arkascha · Accepted Answer · 2015-06-21T07:25:10.537

2

At least you have to include the words with an even number of characters, so:

<palindrome> ::= a | b | aa | bb | a<palindrome>a | b<palindrome>b

edited Jun 21 '15 at 07:25

answered Jun 21 '15 at 06:45

arkascha

41,620
7
58
90

I hear you so if you can walk me through what would be the right way of doing it ? – Jon Abraham Jun 21 '15 at 06:46
That is why I asked about the "arbitrary but fixed" expression. Can't find it on google. Darn, too long ago :-) Looking for an expression to express that "a" in the first line appears before and after the symbol, where "a" can be an arbitrary but fixed character. However a character is defined. That would save the enumeration which feels wrong to me. – arkascha Jun 21 '15 at 06:48
can u tell me if this would be right solution - aabb a aba bbaa b aab aabaa aa bbb baa – Jon Abraham Jun 21 '15 at 06:53
problem is there is not much that i know about this concept. – Jon Abraham Jun 21 '15 at 07:04
The ` ::= *` rule is too generous, I think. You need to allow 0 or 1 letter only, not zero or more. – Jonathan Leffler Jun 21 '15 at 07:04
Yep, all mentionings about repetitions are EBNF, no idea how to express the "*" in the last-but-one line in normal BNF... – arkascha Jun 21 '15 at 07:05
@JonathanLeffler so in that case just use (a,b) only? – Jon Abraham Jun 21 '15 at 07:10
Ah, I just realize: probably my concept cannot be expressed in BNF, since it cannot be expressed by a finite state automaton. It would required an endless number of states... So you'd need a turing machine. – arkascha Jun 21 '15 at 07:10
how would you write that ? – Jon Abraham Jun 21 '15 at 07:12
I saw your original solution in other examples on the web, guess that is where you took it from. But I think we agree that "abba" _is_ a palindrome, so the proposed solution is not complete. That is what I try to fix... – arkascha Jun 21 '15 at 07:13
"how would you write that ?" - as mentioned above: I doubt that _can_ be expressed in BNF, since it has higher complexity. Which surprises me too :-) – arkascha Jun 21 '15 at 07:14
1

I'd probably go with ` ::= | ` where empty denotes no letter. But it isn't well defined — one advantage of [EBNF](http://stackoverflow.com/questions/14922242/how-to-convert-bnf-to-ebnf/14922839#14922839). Note that you don't need to allow for double letters; that's handled by a rule such as `a a` in conjunction with ` := `. – Jonathan Leffler Jun 21 '15 at 07:15
@JonathanLeffler OK, if the alphabet is limited, then indeed this _can_ be expressed by iteration... – arkascha Jun 21 '15 at 07:15
You can just about do it, but it is painful in the extreme to have to write a new term in the main expansion of `` whenever there's a new alphebetic symbol added to the repertoire. OTOH, most people don't go inventing new characters for the alphabet all that often. – Jonathan Leffler Jun 21 '15 at 07:18
@JonathanLeffler Indeed new characters are defined not _that_ often (though it happens, my native language just received a new one some 8 years ago...), but there are already really many characters... – arkascha Jun 21 '15 at 07:19
::= ::= a ::= b ::= aa ::= bb – Jon Abraham Jun 21 '15 at 07:22
Actually, if the BNF supports 'optional' elements, then ` := [ ]` does the ` | ` job. – Jonathan Leffler Jun 21 '15 at 07:22
It does support that, but I doubt that is a palindrome, since I would _not_ consider it to be a word. – arkascha Jun 21 '15 at 07:23
@arkascha i guess the solution that you posted above will work. Hoping i get partial credit for it atleast. – Jon Abraham Jun 21 '15 at 07:27
Let's call the above the result of a combined effort. Allow me to equally spread that upvote to the four of us :) – arkascha Jun 21 '15 at 07:31

BNF grammar for a palindrome

1 Answers1