## finite automata – Theory of Computation

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.

## finite automata – Using Myhill Nerode to prove a language is not regular

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.

## finite automata – prove that if a language is regular then so is the reverse of that language

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

## finite automata – prove that if a language is regular then so is the reverse of that language

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

• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

## automata – How to construct finite automaton

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!

## finite automata – Constructing a NFA from a regular expression

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?

## Cellular Automata: Is there a decentral solution for the Firing Squad Synchronization Problem (FSSP)?

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

## finite automata – Constructing a NFA that accept complement of language L of another NFA

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

## automata – Determine if a Kripke structure satisfies an LTL formula

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.

1. a U b

2. a U X(a ∧ ¬b)

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