All Questions
2 questions
3
votes
1
answer
1k
views
Regular Languages in $ \mathsf{\text{}NC^1}$
Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.
To prove the theorem stated above we need some theorems and definitions given below :
Barrington Theorem : A branching ...
user35837
12
votes
1
answer
433
views
Which non-regular languages are in $AC^0$?
For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.
- 313