While converting each of the final states of F to non-final states of F to final states =, FA thus obtained will reject every string belonging to Land will accept every string, defined over sigma, not belonging to L is called
A] Trnsition Graph of L
B] Regular expression of L
C]Complement of L
D] Finite Automata of L
I think option C is correct.
Please someone correct me if I am wrong.
Let $L$ be your language and let $equiv$ be the equivalence relation defined by $x equiv y$ iff $x in Sigma^*$ and $y in Sigma^*$ have no distinguishing extension (a distinguishing extension is a word $z in Sigma^*$ such that exactly one of $xz$ and $yz$ belongs to $L$).
Given $i,j in mathbb{N}$ with $i < j$, $0^i$ and $0^j$ cannot belong the same equivalence class since $1^i$ is a distinguishing extension for them: $0^i 1^i in L$ but $0^j 1^i notin L$.
This shows that $L/equiv$ is not finite, and hence $L$ is not regular.
Below is a problem from Dexter C Kozen’s Automata and Computability followed by my attempt at a solution. Please provide feedback on my proof. Are there any errors/leaps in logic?
$$$$
Problem Statement
$$$$
My attempt:
$T$ is regular if and only if there exists a NFA accepting $T$. Let $N=(Q,∑,Δ,S,F)$ such that $L(N)=T.$
I will show that there exists a NFA accepting $T$ if and only if there exist a NFA $N_{R}=(Q,∑,Δ_R,S_R,F_R)$ such that $L(N_R)=revT.$
Define: $Δ_R(q,a)={p in Q : q in Δ(p,a)}$, $S_R=F$, $F_R=S$
Lemma 1: if $A⊆Q, $ then $hat{Δ}_R(hat{Δ}(A,x),rev(x))=A$ for all $x in ∑^✱$.
Base Cases:
$$hat{Δ}_R(hat{Δ}(A,ε),ε)=hat{Δ}_R(A,ε)=A$$ by Kozen (6.1). So, equality holds for the empty string.
$$hat{Δ}_R(hat{Δ}(A,a),rev(a))=$$$$bigcup_{qinhat{Δ}(A,a) } {p in Q : q in Δ(p,a) }=$$
$${p in Q : Δ(p,a) ∩ hat{Δ}(A,a) not =∅ }=A$$
by Kozen (6.2), the fact that $rev(a)=a$, and the definition of $Δ_R$.
Inductive Step:
Assume $hat{Δ}_R(hat{Δ}(A,x),rev(x))=A$.
$$hat{Δ}_R(hat{Δ}(A,xa),rev(xa))=hat{Δ}_R(hat{Δ}(A,xa),arev(x))=$$
by definition of string reversal in problem statement.
$$hat{Δ}_R(bigcup_{qinhat{Δ}(A,x)}Δ(q,a), arev(x)) $$
by Kozen definition (6.2) page 33
$$bigcup_{qinhat{Δ}(A,x)}hat{Δ}_R(Δ(q,a), arev(x)) $$
by Kozen Lemma 6.2 page 34
$$bigcup_{qinhat{Δ}(A,x)}hat{Δ}_R(hat{Δ}_R(Δ(q,a), a),rev(x))= $$
by Kozen Lemma 6.1
$$hat{Δ}_R(hat{Δ}_R(hat{Δ}(A,xa), a),rev(x))= $$
by Kozen Lemma 6.2
$$hat{Δ}_R(hat{Δ}_R(hat{Δ}(hat{Δ}(A,x),a), rev(a)),rev(x))= $$
by Kozen Lemma 6.1 and by the fact that $rev(a)=a$
$$hat{Δ}_R(hat{Δ}(A,x),rev(x))= $$
by the base case for a single character
$$A$$ by assumption.
Lemma 2: $hat{Δ}(A ∩ B,x)= hat{Δ}(A,x) ∩ hat{Δ}(B,x)$
Base Case:
$hat{Δ}(A ∩ B,ε)=A ∩ B= hat{Δ}(A,ε) ∩ hat{Δ}(B,ε)$ by definition (6.1) kozen
Inductive step:
Assume $hat{Δ}(A ∩ B,x)= hat{Δ}(A,x) ∩ hat{Δ}(B,x)$
$$hat{Δ}(A ∩ B,xa)=bigcup_{qinhat{Δ}(A∩ B,x)}Δ(q,a)=$$
by definition (6.2) kozen
$$bigcup_{qin(hat{Δ}(A,x)∩ hat{Δ}( B,x))}Δ(q,a)=$$
by assumption
$$bigcup_{qinhat{Δ}(A,x)}Δ(q,a)∩bigcup_{qinhat{Δ}(A,x)}Δ(q,a)=hat{Δ}(A,xa)∩hat{Δ}(B,xa)$$
by definition (6.2) kozen and basic set theory
Now I will use lemma 1 and lemma 2 to show $x in L(N)$ IFF $rev(x) in L(N_R)$
$x in L(N)$ IFF $hat{Δ}(S,x)∩F not = ∅$ IFF
$hat{Δ_R}(hat{Δ}(S,x)∩F,rev(x)) not = hat{Δ_R}(∅,rev(x)) $ IFF
$hat{Δ_R}(hat{Δ}(S,x),rev(x)) ∩hat{Δ_R}(F,rev(x)) not = ∅ $, by lemma 6.2, IFF
$S ∩hat{Δ_R}(F,rev(x)) not = ∅ $, by lemma 6.1, IFF
$F_R ∩hat{Δ_R}(S_R,rev(x)) not = ∅$, by definition of $F_R,S_R$, IFF
$rev(x) in L(N_R)$ $∎$
Pasted below is a problem from Dexter C Kozen’s Automata and Computability followed by my attempt at a solution. I would appreciate feedback on my proof. Are there any errors/leaps in logic? If having access to the text would be helpful, I am happy to post a link, assuming that doing so is permissible on this form.
$$$$
$$$$
My attempt:
If $T$ is regular then there exists a NFA accepting $T$. Let $N=(Q,∑,Δ,S,F)$ such that $L(N)=T.$ I will show that there exists a NFA $N_{R}=(Q,∑,Δ_R,S_R,F_R)$ s.t $L(N_R)=revT.$
Define: $Δ_R(q,a)={p in Q : q in Δ(p,a)}$, $S_R=F$, $F_R=S$
Lemma 1: if $A⊆Q, $ then $hat{Δ}_R(hat{Δ}(A,x),rev(x))=A$ for all $x in ∑^✱$.
Base Cases:
$$hat{Δ}_R(hat{Δ}(A,ε),ε)=hat{Δ}_R(A,ε)=A$$ by Kozen (6.1). So, equality holds for the empty string.
$$hat{Δ}_R(hat{Δ}(A,a),rev(a))=$$$$bigcup_{qinhat{Δ}(A,a) } {p in Q : q in Δ(p,a) }=$$
$${p in Q : Δ(p,a) ∩ hat{Δ}(A,a) not =∅ }=A$$
by Kozen (6.2), the fact that $rev(a)=a$, and the definition of $Δ_R$.
Inductive Step:
Assume $hat{Δ}_R(hat{Δ}(A,x),rev(x))=A$.
$$hat{Δ}_R(hat{Δ}(A,xa),rev(xa))=hat{Δ}_R(hat{Δ}(A,xa),arev(x))=$$
by definition of string reversal in problem statement.
$$hat{Δ}_R(bigcup_{qinhat{Δ}(A,x)}Δ(q,a), arev(x)) $$
by Kozen definition (6.2) page 33
$$bigcup_{qinhat{Δ}(A,x)}hat{Δ}_R(Δ(q,a), arev(x)) $$
by Kozen Lemma 6.2 page 34
$$bigcup_{qinhat{Δ}(A,x)}hat{Δ}_R(hat{Δ}_R(Δ(q,a), a),rev(x))= $$
by Kozen Lemma 6.1
$$hat{Δ}_R(hat{Δ}_R(hat{Δ}(A,xa), a),rev(x))= $$
by Kozen Lemma 6.2
$$hat{Δ}_R(hat{Δ}_R(hat{Δ}(hat{Δ}(A,x),a), rev(a)),rev(x))= $$
by Kozen Lemma 6.1 and by the fact that $rev(a)=a$
$$hat{Δ}_R(hat{Δ}(A,x),rev(x))= $$
by the base case for a single character
$$A$$ by assumption.
Lemma 2: $hat{Δ}(A ∩ B,x)= hat{Δ}(A,x) ∩ hat{Δ}(B,x)$
Base Case:
$hat{Δ}(A ∩ B,ε)=A ∩ B= hat{Δ}(A,ε) ∩ hat{Δ}(B,ε)$ by definition (6.1) kozen
Inductive step:
Assume $hat{Δ}(A ∩ B,x)= hat{Δ}(A,x) ∩ hat{Δ}(B,x)$
$$hat{Δ}(A ∩ B,xa)=bigcup_{qinhat{Δ}(A∩ B,x)}Δ(q,a)=$$
by definition (6.2) kozen
$$bigcup_{qin(hat{Δ}(A,x)∩ hat{Δ}( B,x))}Δ(q,a)=$$
by assumption
$$bigcup_{qinhat{Δ}(A,x)}Δ(q,a)∩bigcup_{qinhat{Δ}(A,x)}Δ(q,a)=hat{Δ}(A,xa)∩hat{Δ}(B,xa)$$
by definition (6.2) kozen and basic set theory
Now I will use lemma 1 and lemma 2 to show $x in L(N)$ IFF $rev(x) in L(N_R)$
$x in L(N)$ IFF $hat{Δ}(S,x)∩F not = ∅$ IFF
$hat{Δ_R}(hat{Δ}(S,x)∩F,rev(x)) not = hat{Δ_R}(∅,rev(x)) $ IFF
$hat{Δ_R}(hat{Δ}(S,x),rev(x)) ∩hat{Δ_R}(F,rev(x)) not = ∅ $, by lemma 6.2, IFF
$S ∩hat{Δ_R}(F,rev(x)) not = ∅ $, by lemma 6.1, IFF
$F_R ∩hat{Δ_R}(S_R,rev(x))$, by definition of $F_R,S_R$, IFF
$rev(x) in L(N_R)$ $∎$
Thanks for contributing an answer to Computer Science Stack Exchange!
But avoid …
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
So I have been working on a homework question and I just can’t seem to make any progress on this question. So far I have been trying to figure out a regular pattern in 504 and have broke it down to the prime factorization of 504 = (2^3)(3^2)(7). Which means all divisors must be a multiple of 2,3, or 7. However I don’t know how to create the finite automaton (NFA or DFA). Any help is appreciated!
I have the following regular expression $R=ab^*(epsilon cup c) cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression.
I started by constructing the NFA that accepts $R=ab^*(epsilon cup c)$
Next I tried to continue the concatenation part by adding the following to the NFA as follows:
Is that correct? is there a quick approach to construct NFA from long regular expressions?
is there a decentral solution for the FSSP, that is, where it is arbitrary which of all the automata is the first general?
Thanks
von Spotz
Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.
Is there a polynomial time way to do it? I don’t know, since the construction above can be exponential time in the number of states (because of the powerset construction).
I am trying to understand the correlation between LTL and Kripke structures. Zoom classes are very tough to follow and i can’t find anything online. I have the following Kripke structure with q3 as start. I have to demonstrate that it either satisfies or not the following LTL formulae.
a U b
a U X(a ∧ ¬b)
X¬b ∧ G(¬a ∨ ¬b)
I would really appreciate if somebody could explain to me the steps to prove that a KS satisfies a LTL formula.
