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$.

$$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

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$.

$$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

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 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.