CFG-Infinite recursion
-
29-09-2020 - |
Question
As you see, the string production process never ends.
Can someone explain me if this language is regular or not ?
$ S \to Α Β S $
$ A \to S $
$ B \to a B b $
Solution
The language is regular: $$ L = \{\}$$ It doesn't contain any word not even the empty word $\varepsilon$. The automaton recognizing it has only one state; a reject state. Or if you are using DFA the automaton just wouldn't have an accept state.
Notice that the language is regular but that the grammar is written in a form that's usually used for context free grammars, but the language produced by it is still regular.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange