Tagged Questions

2
votes
1answer
103 views

Would the following NFA accept all strings?

The question asks the following: "Let N be a nondeterministic finite automaton with s states. Suppose than N accepts all strings of length s or less. Does it follow that N accepts all strings? (If so, ...
1
vote
1answer
88 views

How would I go about proving for this NFA?

I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following: N accepts the string x if the number of distinct ...
0
votes
1answer
33 views

How can I prove a DFA accepts a certain mininum number of states?

We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
1
vote
1answer
94 views

Nondeterministic finite automaton proof

I am having a really hard time working the problem below out. I am not sure I am even on the right direction with this logic . Swapping the accept and reject states alone is not sufficient to accept ...
1
vote
1answer
111 views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...
2
votes
1answer
47 views

Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
0
votes
2answers
98 views

Proof Two Grammars Generate the Same Language

I have two right linear grammars and I need to prove they both generate the same language. What is the right way to do it? L1: $S \rightarrow 0A$ $S \rightarrow 1B$ $A \rightarrow 0A$ $A ...
1
vote
1answer
43 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
223 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$ ...
0
votes
0answers
55 views

Confusion about proving equivalence of two states in FSM

There is this proof: M = (Q,S,R,f,g). where Q is the set of states, S input alphabet, R output alphabet, f state transition function Q X S => Q, g output funtion Q => R Suppose that q1, q2 are two ...
0
votes
0answers
34 views

Proof two FSM are k-equivalent [duplicate]

Possible Duplicate: Confusion related to state equivalence of finite state machines Show that p is k-equivalent to q, if and only if that any x belongs to S*, |x|=k, g(p,x)=g(q,x) Any ...
1
vote
1answer
92 views

finite state machine is strongly connected

Let M be an n-state reduced strongly connected finite state machine. prove there exists an input string $w$, where $|w|\le n(n-1)/2$, s.t. M assumes each of its states at least once in response to ...
0
votes
2answers
107 views

How to represent a formal proof

I know how I want to do the proof, but I don't know how to represent it. It's an automata proof, so all I need to do is show that it is regular. How could I represent a DFA as a copy? So I have the ...