CODEWITHSUNDEEP
grammarbnfebnf
John
John

Reputation:

Defining a language in EBNF

Give the EBNF specification for the language L that is made up of the chars a, b and c such that sentences in the language have the form

L : sqsR

-s   is a string of any combination of the characters a and b
-sR  is that same string s reversed
-q   is an  odd number of c's followed by either an odd number of b's
     or an even number of a’s.

What I have so far:

L -> S
S -> {a}{b}Q
Q ->

If this is right, I'm still not really sure how to produce from Q and also how to represent S in reverse.

Upvotes: 1

Views: 972

Answers (2)

1800 INFORMATION
1800 INFORMATION

Reputation: 135285

This is a string that starts and ends with the same string, but reversed:

X -> aXa
  -> bXb

This is a string with an odd number of c's:

Y -> cY2
Y2 -> ccY2

I've left out some crucial bits, but hopefully this can get you started.

Upvotes: 2

dmckee --- ex-moderator kitten
dmckee --- ex-moderator kitten

Reputation: 101181

  • Try building the first two parts from the middle out
  • You can force an odd number of repetitions by starting with exactly one item and adding N*2 additional items (for integer N). This should suggest how to force an even number as well

Upvotes: 1

Related Questions