HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to find whether a grammar's language is finite or infinite?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitefinitehowlanguagegrammarfindwhether

Problem

I have this context-free grammar and I want to find out whether its language is finite or infinite.

S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3


So I would do

S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb


So I know how to generate words like this but how to find out whether the language is finite or infinite?

Solution

A language is infinite if it can generate infinitely many words. In order to prove that a language generated by a grammar is infinite, you need come up with some infinite list of words generated by the grammar. Proving that the language is finite is slightly more messy—you need to make a list of all possible derivations, and show that all of the terminate.

In your case, you have the derivation $S\to^*SSSS$, which suggests that the language is infinite. Can you come up with an infinite list of words generated by this grammar?

Context

StackExchange Computer Science Q#23367, answer score: 8

Revisions (0)

No revisions yet.