If you can show that S goes to something and itself ex: S->bS then your language is infinite. If someone attempted to make a finite list of everything the language could represent, you could always legally create something one 'b' character longer than anything in his finite list. Therefore any finite list isn't actually a complete list of everything the language could produce and the language is infinite.
How to come up with a solution of finite or infinite language using context free grammar?
-
26-06-2023 - |
Вопрос
I am trying to come up with a solution of finite or infinite language using context free grammar.
I have these grammars to find if it's a solution of finite or infinite language
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 here how to generate a word like this, but how do I find if its finite or infinite language?
Решение
Не связан с StackOverflow