0
votes
1answer
28 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
1
vote
1answer
47 views

Show Two f.s.a. machines accept different input

I'm trying to solve it for two hours already. I know it somehow related to the pumping lemma Let $M_1 = \langle Q_1,S,f_1,s_1,F_1\rangle$ and $M_2 = \langle Q_2,S,f_2,s_2,F_2\rangle$ be two machines, ...
1
vote
1answer
827 views

Show two finite state machines are equivalent

Suppose $M_1 = \langle Q_1,S,R,f_1,g_1\rangle$ and $M_2 = \langle Q_2,S,R,f_2,g_2\rangle$ are two strongly connected machines. I need to show that $M_1 \equiv M_2$ iff there exist a state $p \in Q_1$ ...