CODEWITHSUNDEEP
bnf
Barqs
Barqs

Reputation: 33

Consider the following BNF grammar (BNF, Recursion, and Derivation)

Consider the following BNF grammar:

<S> ::= a <S> c <B> | <A> | b
<A> ::= c <A> | c
<B> ::= d | <A>

ok, so then i am given various strings, one which is:

aabccd

If the string can be derived from the BNF grammar, then I should provide a derivation.

So I start with a non-terminal (from what I understand):

<S> ::= a <S> c <B> -> a a <S> c <B> c <B> -> a a b c <B> c <B> ->
a a b c <A> c <B> -> a a b c c c <B> ->  a b c c c d

Is this correct? Therefore it can't be derived? because i have three Cs? Or did I do it wrong. Total n00b when it comes to BNF.

edit: Ok, looking at it from a more "free" approach. Would it be valid/legal to convert the terminal/token known as "c" along with the non-terminal <A>, in other words "c <A>", within the string to simply "c"? Given that "c A" are an "A"? Therefore allowing me to convert them to simply "c". Which would then allow me to acquire the string requested:

<S> ::= a <S> c <B> -> a a <S> c <B> c <B> -> a a b c <B> c <B> ->
a a b c <A> c <B> -> a a b c c <B> ->  a a b c c d

Valid?

Edit: I don't know how to make the less than and greater than symbols appear, tried using the dollar signs but I guess it doesn't work here.

Upvotes: 0

Views: 1326

Answers (2)

Bob Jarvis - Слава Україні
Bob Jarvis - Слава Україні

Reputation: 50017

Your first derivation is correct, and 'aabccd' doesn't parse using this grammar. You'd need a third 'c' for it to be parse-able - so 'aabcccd' could be parsed, but not 'aabccd'.

Best of luck.

Upvotes: 1

J. Birkner
J. Birkner

Reputation: 56

Since your grammar is context-free, you can convert it to Chomsky Normal Form (CNF) and apply the CYK (Cooke-Young-Kasemi) algorithm to check whether the word is part of L(G), to have a guess-free, deterministic approach.

Upvotes: 1

Related Questions