I've been looking online for quite some time for some 'general' rules on this.

for example, there's a 'rule' that claims that if a language is like $$L={w\in {a,b,c}^* : count_\alpha (w) =count_\beta (w) \pm count_\gamma (w) }$$ where $\alpha , \beta , \gamma $ could take on the form of one of the characters in $\Sigma$

However, we know that if the condition has multiplication/division instead of adding/subtracting, the language becomes non-context free, which makes sense.

However, I'm looking for more rules like such, for regular languages/CFLs and also for being able to distinguish if a language is decidable, non decidable but recognizable, or neither

thanks in advance.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.