Re: What is the language of this grammar?

surmoi@xxxxxxxxx writes:

S-> xSS | y
L(G) = ?

I only know the number of y is 1 more than the number of x, and y is
the ending character.
How do I describe it?

If you delete the last y, you can read x as opening bracket and y as
closing bracket and what you get is the set of balanced bracket
sequences.

You can prove this by induction:

Base case: S => y, delete y, empty string is balanced.

Induction step: Assume true for S=>v, S=>w. xv is then balanced, as
x matches the y at the end of v. Hence, xvw is balanced after
removing the y at end of w.

Torben



.

Relevant Pages

  • Re: Bit missing from Sparkle 9800GT box
    ... I can't take advantage of the free return postage as its with Royal ... Mail and I have Jerseymail to go thru first, secondly by removing the ... full height bracket completely leaving no bracket I can install the ...
    (uk.comp.homebuilt)
  • Re: Tech EM: Gottlieb Big Brave Flipper Bounce - Coil Question
    ... I was thinking about removing the piece of black plastic from ... stiffen up the system at the end of the stroke. ... I believe they serve to help isolate the stop from the whole bracket ... magnetic sticking. ...
    (rec.games.pinball)
  • Re: P70 plasma left mounting bracket?
    ... What happened was I didn't have the HMS or HRS handy so I ended up ... removing the screen in some weird way that split the left bracket in ...
    (comp.sys.ibm.ps2.hardware)