CODEWITHSUNDEEP
recursionbnf
Bjelica Vesely
Bjelica Vesely

Reputation: 11

Consider the following BNF grammar (BNF, Recursion)

Write a BNF grammar for recognizing all sentences in the form of anbn-2, where n>1.
For example, aa, aaab, aaaabb are all accepted,
but abbb, aab, aabb are not
(Hint: use recursion).

This is my derivation:
S ::= AZ
Z ::= A | AAB
A ::= a
B ::= b
Is this correct?

EDIT: Maybe this is correct?

S -> a | X | Y
X-> aX | a
Y -> aX | b

Upvotes: 1

Views: 533

Answers (2)

beatngu13
beatngu13

Reputation: 9373

Your first grammar only produces:

S -> AZ -> aZ -> aa
S -> AZ -> aZ -> aAAB -> aaab

Your second grammar allows words containing only a's, which are not part of the language. For instance:

S -> a

I'd simply start with two a's and then produce arbitrary pairs. Hence, the grammar looks like (BNF syntax):

<term> ::= "aa" | "aa" <pair>
<pair> ::= "ab" | "a" <pair> "b"

Example:

<term> -> "aa"
<term> -> "aa" <pair> -> "aaab"
<term> -> "aa" <pair> -> "aaa" <pair> "b" -> "aaaabb"
...

Upvotes: 0

user31264
user31264

Reputation: 6727

Both are completely incorrect.

First grammar: since A turns only to a, and B only to b, we can replace A by a and B by b. The grammar will be:

S -> aZ
Z -> a
Z -> aab

Thus, S turns to either aa or aaab, but not, for example, aaaabb.

Second grammar: use the first rule and turn S to a. Since a is not a valid word, the grammar is also incorrect. (Alternatively, we could turn S to X, then X to aX 9 times, then X to a, making aaaaaaaaaa, which is also invalid).

Upvotes: 0

Related Questions