snippetMinor
How to find whether a grammar's language is finite or infinite?
Viewed 0 times
infinitefinitehowlanguagegrammarfindwhether
Problem
I have this context-free grammar and I want to find out whether its language is finite or infinite.
So I would do
So I know how to generate words like this but how to find out whether the language is finite or infinite?
S -> XY|bb Step 1
X -> XY|SS Step 2
Y -> XY|SS Step 3So 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
bbbbbbbbbbbbSo 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?
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.