CODEWITHSUNDEEP
algorithmparsinggrammar
D1X
D1X

Reputation: 5444

Regular grammar produced strings?

I have a paper that states:

(...) languajes such as strings of x's followed by the same number of y's (for example xxxxyyyy) cannot be specified by a regular grammar or Finite States Automaton because these devices have no mechanism for remembering how many x's were generated when the time comes to derive the y's. This shortcoming is remedied by means of rules such as S → xSy, which always generate an x and a y at the same time. (...)

So, I don't understand this statement, as far as I know, such strings can be generated with the regular grammar with production rules:

S → xS

S → yS

S → y

Where x,y are terminals, S is the starting unique non terminal. This grammar produces the derivation

S→xS→xxS→xxxS→xxxxS→xxxxyS→xxxxyyS→xxxxyyyS→xxxxyyyy

Upvotes: 0

Views: 94

Answers (1)

user2512323
user2512323

Reputation:

Grammar must generate every string in language, and no strings not in language.

Your grammar also generates invalid string y with the third production, or xxy, or xyxy, hence you can NOT say this is a grammar for your language.

Upvotes: 2

Related Questions