Give a Regular Language L

Question

Give a regular grammar for L= {a^n b^n : n<=100}

I would do something like this :

s---> A | empty string

A---> aB| empty String

b---> Ab

but How do we keep count of the number in the grammar? meaning How does it know when there are more that 100 a's. Also I'm not even sure if my way makes sense.

Any help would be appreciated.

If a language is finite then you have to write (long grammar) like Sirko suggesting in his answer no other choice. Also your grammar is Context Free grammar not regular, read: [Why this is not regular language?](http://stackoverflow.com/questions/16723185/is-ab-regular?answertab=votes#tab-top) – — Grijesh Chauhan, May 28 '13 at 07:34

score 3 · Answer 1 · answered May 27 '13 at 22:09

3

As the members of this language are clearly limited, you can just give them as a listing of all possible cases:

S -> ab | aabb | aaabbb | ... | a^100b^100

answered May 27 '13 at 22:09

Sirko

72,589
19
149
183

score 0 · Answer 2 · edited May 28 '13 at 07:32

0

Let's say that S is the start symbol:

1) S -> aXb
2) X -> aXb 
3) X -> ab

And I can prove this works:
1) S -> aXb
2) aXb -> a aXb b
... (n-3) times

a^(n-1) X b^(n-1) -> a^n b^n (using the third rule, X -> ab)

edited May 28 '13 at 07:32

Grijesh Chauhan

57,103
20
141
208

answered May 27 '13 at 22:13

Alin Ciocan

3,082
4
34
47

1

This won't take care of the `n<=100` part. – Sirko May 27 '13 at 22:15
1

Also, this is a context-free grammar, not a regular grammar. – templatetypedef May 27 '13 at 22:59

Give a Regular Language L

2 Answers2