In <···············@iowasp.physics.uiowa.edu> ·····@iowasp.physics.uiowa.edu writes:
> I recently had a question asked about BNF definitions for a Programming
> Languages Course. The question is as follows:
>
> Using character set C={a,b} write a BNF definition for the language
> consisting of all strings with odd length whose first and middle characters are
> the same.
>
> If anyone can help it would be greatly appreciated.
> e-mail: ·····@iowasp.physics.uiowa.edu
Let G be the context free grammar G = (V,T,P,S) with nonterminals
V = {S, X, A, B}, terminals C = T = {a, b}, axiom S, and the production
rules P as follows:
S -> aAX | bBX | a | b
X -> a | b
A -> a | XAX
B -> b | XBX
This should be expressible in your favourite BNF notation,
too. Perhaps someone could find a smaller set of productions.
-- Wolfgang
--
Dr. Wolfgang Goerigk ( ··@informatik.uni-kiel.d400.de )
University of Kiel (CAU) phone: ++49-431-5604-24
D-24105 Kiel, Germany fax : ++49-431-566143