Skip to content

Latest commit

 

History

History
449 lines (386 loc) · 18.2 KB

assignment-11.org

File metadata and controls

449 lines (386 loc) · 18.2 KB

Assignment 11, Authomata Theory

Problems

Problem 1

Given following languages over the alphabet $\{a, b\}$

  • $L_1 = ∅$.
  • $L_2 = \{ε, aa\}$.
  • $L_3 = \{ε, a, aa, ab, abb\}$.
  • $L_4 = \{aabb, aabbb, aa, aaa\}$.
  • $L_5 = \{ε, b, bbb, abab, abba, aabb\}$.
  • $L_6 = \{ε, bbbaa, baba, aaab, aabba, aa\}$.
  1. What are the following languages:
    • $L_4L_4$.
    • $(L_1 ∪ L_2 ∪ L_3)^R$.
    • $L_3L_1L_6$.
  2. Define exponentiation as follows: $L^K = \{x ∈ L \;|\; ∃ y ∈ K.(\abs{y} = \abs{x})\}$. What are the languages $L_4L_5$ and $L_6L_1$?

Answer 1

  1. Concatenation of $L_4$ with itself gives: $L_4L_4 = \{aabbaabb, aabbaabbb, aabbaa,\;$ $aabbaaa, aabbbaabb, aabbbaa, aabbbaaa, aaaabbb, aaaa, aaaaa, aaaaabb, aaaaabbb\}$
  2. $(L_1 ∪ L_2 ∪ L_3)^R = \{ε, a, aa, ba, bba\}$.
  3. $L_3L_1L_6 = ∅$. This is so because there are no words in language $L_1$ to concatenate with.
:- use_module(library(lists)).

concatentated_member(L1, L2, L3) :-
    member(M1, L1), member(M2, L2),
    string_concat(M1, M2, L3).

concatentated(L1, L2, L3) :-
    findall(X, concatentated_member(L1, L2, X), X),
    list_to_set(X, L3).

assignment_11a :-
    X = ["aabb", "aabbb", "aa", "aaa"],
    concatentated(X, X, Y),
    [First | Rest] = Y,
    write("$$\\{"),
    write(First),
    maplist(format(',\\allowbreak ~s'), Rest),
    write("\\}$$").

Answer 2

  1. $L_4L_5 = \{aaa, aabb\}$.
  2. $L_6L_1 = ∅$.

Problem 2

Let $L_1, L_2$ and $L_3$ be languages over some alphabet $Σ$. Prove or disprove:

  1. $(L_1 ∪ L_2) L_3 = L_1 L_3 ∪ L_2 L_3$.
  2. $(L_1 ∩ L_2) L_3 = L_1 L_3 ∩ L_2 L_3$.

Answer 3

First, I will prove $(L_1 ∪ L_2) L_3 ⊂ L_1 L_3 ∪ L_2 L_3$. Assume to the contrary that there is $w ∈ (L_1 ∪ L_2) L_3$ which is not in $L_1 L_3 ∪ L_2 L_3$. Put $w = xy$ where $x ∈ (L_1 ∪ L_2)$ and $y ∈ L_3$ (this implies $L_3 ≠ ∅$ and at least one of $(L_1 ∪ L_2) ≠ ∅$. Suppose $x$ comes from $L_1$, then it has to be in $L_1 L_3 ∪ L_2 L_3$ because it is in L_1 L_3$, similartly if it originates in $L_2$. Suppose now $L_3 = ∅$, then there is an empty set on both sides of equation (by definition of concatenation). Suppose both $L_1$ and $L_2$ are empty, then, again, we have emtpy set on both sides of the equation. Thus we showed that it is impossible for $w$ not to be in the $L_1 L_3 ∪ L_2 L_3$, hence the original argument must be true.

Similarly, to prove $L_1 L_3 ∪ L_2 L_3 ⊂ (L_1 ∪ L_2) L_3$, assume there exists $w ∈ L_1 L_3 ∪ L_2 L_3$, not a amember of $(L_1 ∪ L_2) L_3$. Again, $w = xy$ where $y ∈ L_3$ and $x$ may be a member of $L_1$, $L_2$ or both. Suppose, again, the sets aren’t empty. If $w$ came from $L_1 L_3$, then $x$ came from $L_1$, but it is a member of $(L_1 ∪ L_2)$ and similarly if it came from $L_2$. Since $y ∈ L_3$ and $L_3$ is present on both sides, it is not possible for $w$ to not be a member of $(L_1 ∪ L_2) L_3$. As in previous case, whenever $L_3$ or $(L_1 ∪ L_2)$ are empty, both sides of equation contain an empty set. Hence we proved both directions, hence the conjecture is true.

Answer 4

This conjecture isn’t generally true. Suppose $L_1 = L_3 = \{a\}$ and $L_3 = \{ε, aa\}$. Then:

  1. $(L_1 ∩ L_2) L_3 = ∅$.
  2. $L_1 L_3 ∩ L_2 L_3 = \{aa\}$.

I.e. both sides of equation are not equal. This completes the proof.

Problem 3

An equivalence relation over $Σ^*$ will be called invariant from right if $∀ z ∈ Σ^*.(xRy \implies xzRyz)$. Answer for every relation in $\{a, b\}^*$ whether the relation is an equivalence relation and whether it is invariant from right.

  1. $xRy \iff \abs{x} \geq \abs{y}$.
  2. $xRy \iff (\abs{x} = \abs{y} = 0 ∨ x = qz, y = pz, \abs{z} \geq 1)$.

Answer 5

Total order relation is not symmetric. Suppose $x = a$ and $y = ab$, then $x \geq y$ but not $y \geq x$. Since this relation is not an equivalence, it cannot be right invariant either.

Answer 6

This relation is an equivalence. It is transitive because whenever $x = qz$, $y = pz$ and $w = vz$, all of the below hold: $xRy$, $yRw$, $xRw$ since they all have the last letter in common. This also holds trivially in case the length is zero, since $x = y = w = ε$ in that case.

The relation is reflexive because whenever every string is either empty or its last symbol is equal to itself, i.e. $xRx$ is always true.

The relation is symmetric because whenever $x = qz$ and $y = pz$ then both $xRy$ and $yRx$ hold (again, becuase $x$ and $y$ have the final letter in common, or are both the empty string).

The relation is also invariant from the right. The proof will proceed by induction on the string’s length.

Base step: $ε R ε \implies ε z R ε z$ because $R$ is reflexive and $z = ε z$.

Inductive step: suppose the inductive hypotesis $xRy \implies xzRyz$, then suppose we concatenate the same character $c$ to both $x$ and $y$. This character must be the same by definition of $R$. Then $xcRyc \implies xczRycz$ because we can simply rename $xc = x_1$ adn $yc = y_1$ and obtain the inductive hypothesis restated using new terms: $x_1Ry_1 \implies x_1zRy_1z$. This completes the inductive step, and hence the proof is completed.

Problem 4

Build an DFA accepting languages over alphabet $\{a, b\}$ s.t.

  1. The language contains all words with a substring $abb$, but never with the substring $aa$.
  2. If the word contains substring $bb$ must, it must be preceded by $aba$.

Answer 7

Below is the DFA for the first question:

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick]

  \node[initial,state]    (A)              {$q_a$};
  \node[state]            (B) [right of=A] {$q_b$};
  \node[state]            (C) [right of=B] {$q_c$};
  \node[accepting,state]  (D) [right of=C] {$q_d$};
  \node[accepting,state]  (E) [below of=D] {$q_e$};

  \path (A) edge [loop above] node {b}   (A)
            edge              node {a}   (B)
        (B) edge              node {b}   (C)
        (C) edge              node {a}   (B)
            edge              node {b}   (D)
        (D) edge [loop above] node {b}   (D)
            edge              node {a}   (E)
        (E) edge [loop left]  node {b}   (E)
            edge              node {a}   (D);
\end{tikzpicture}

Nodes where the automata dies are not shown.

Answer 8

Below is the DFA for the second question:

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick]

  \node[accepting,initial,state] (A)              {$q_a$};
  \node[accepting,state]         (B) [below of=A] {$q_b$};
  \node[accepting,state]         (C) [below of=B] {$q_c$};
  \node[accepting,state]         (D) [right of=C] {$q_d$};
  \node[state]                   (E) [above of=D] {$q_e$};
  \node[accepting,state]         (F) [above of=E] {$q_f$};
  \node[accepting,state]         (G) [right of=D] {$q_g$};
  \node[accepting,state]         (H) [left of=B]  {$q_H$};

  \path (A) edge node {a} (B)
            edge node {b} (H)
        (B) edge node {b} (C)
        (C) edge node {a} (D)
        (D) edge node {b} (E)
            edge node {a} (B)
        (E) edge node {b} (F)
            edge node {a} (G)
        (F) edge node {a} (B)
        (G) edge node {a} (D)
            edge node {b} (E)
        (H) edge node {a} (A);
\end{tikzpicture}

Nodes where the automata dies are not shown.

Problem 5

Given alphabet of binary strings and netation operation defined as follows:

\begin{align*}
  \Neg(w) = \begin{cases}
    \epsilon  &\mbox{if } w = \epsilon \\
    1         &\mbox{if } w = 0 \\
    0         &\mbox{if } w = 1 \\
    0.\Neg(y) &\mbox{if } w = ay \land a = 1 \\
    1.\Neg(y) &\mbox{if } w = ay \land a = 0\;.
  \end{cases}
\end{align*}

And similarly for languages: $\Neg(L) = \{w \;|\; \Neg(w) ∈ L\}$.

  1. Does there exist a language $\overline{L} = \Neg(L)$?
  2. Does there exist a language $\overline{L} \setminus \{ε\} = \Neg(L)$?

Answer 9

No, there cannot be such language. Suppose there was such a language, then $ε$ must be either in it or in its complement. Suppose $ε$ is part of $L$, then it must be also in its negation since $ε = \Neg(ε)$. By symmetric reasoning $ε$ cannot be in $\overline{L}$.

Answer 10

Yes, there exists such a language, for instance the language representing all odd numbers in base 2. Its complement would be a language representing all even numbers in base 2 and because words in $L$ always end in 1 (with no other requirements) negating them will necessarily produce a word in $\overline{L}$.

No number is both odd and even, therefore negation produces exactly the complement of $L$. Since empty string is excluded, the only word which would be also a negation of itself is excluded as well.

Problem 6

  1. Given DFAs $A = (Σ, Q, q_0, F, δ)$ and $B = (Σ, Q, q_0, F ∩ (Q \setminus q_0), δ)$, is it also the case that $L(B) = L(A) ∩ Σ^+$?
  2. Given DFA $A = (Σ, Q, q_0, F, δ)$ construct DFA $B$ from $A$ s.t. it accepts all words of the language of $A$ which have length distinct from 1.

Answer 11

The conjecture is false. Consider the language of unary strings of even length described by the following transitions table:

$δ$ a
$*q_0$ $q_1$
$q_1$ $q_0$

In other words, $L(A) = \{ε, aa, aaaa, aaaaaa, …\}$. However $F \setminus \{q_0\} = ∅$, i.e. no words are accepted by $L(B)$, while $L(A) ∩ Σ^+ = \{aa, aaaa, aaaaaa, …\}$.

Answer 12

A DFA can accept words of length 1 in only these two scenarios:

  1. It loops on some input in the first accepting state.
  2. The state directly linked from the first state is accepting.

Below is the procedure to remove these accepting states while accepting all other inputs.

  1. If the first state loops on some inputs add a new state $q_1$, remove all transitions from $q_0$ to itself and add transitions for the same inputs $I_0$ from $q_0$ to $q_1$. Add transitions on all inputs from $q_1$ back to itself.

    For any input which on which $q_0$ used to loop $B$ now necessary makes at least two transitions before accepting it, possibly accepted string with prefixes that did not cause the automate to loop on $q_0$ are still accepted (nothing has changed).

  2. For each accepting state $q_n$ directly linked from $q_0$ we do the following:
    • change $q_n$ from accepting to non-accepting.
    • add a new accepting state $q_2$.
    • remove transitions from states $Q_i$ directly to $q_n$, for each transition removed add a new one for the same input from $Q_i$ to $q_2$.
    • for each outbound transition from $q_n$ add new transition on the same input from $q_2$.
\begin{algorithm}
  \caption{Ensure the language of this DFA has no words of length 1}
  \begin{algorithmic}
    \Procedure {$\textit{ensure-word-length-ne-one}$}{$\Sigma, Q, q_0, F, \delta$}
      \State $loops \gets \{i \;|\; \exists i \in \Sigma. (\delta(q_0, i) = q_0)\}$
      \State $new \gets \textit{make new accepting state}$
      \State $backarcs \gets \{(v, w, i) \;|\; 
      \exists v,w \in Q. (\delta(q_0, j) = v = \delta(w, i) \land i \neq q_0)\}$
      \For {$input \in loops$}
        \State \Comment{Remove all loops from the first state}
        \State \Call {$\textit{add-transition}$}{$q_0, new, input$}
        \State \Call {$\textit{remove-transition}$}{$q_0, q_0, input$}
        \State \Call {$\textit{add-transition}$}{$new, new, input$}
      \EndFor
      \For {$input \in \Sigma$}
        \State \Comment{Bounce back from the new state to the first state}
        \State \Call {$\textit{add-transition}$}{$new, q_0, input$}
      \EndFor
      \For {$(source, destination, input) \in backarcs$}
        \State \Comment{For each state directly reachable \\
          \hspace{6.7cm} from the first state reattach \\
          \hspace{6.7cm} all inbound transitions \\
          \hspace{6.7cm} to the new state}
        \State $new \gets \textit{make new accepting state}$
        \State \Call {$\textit{remove-transition}$}{$source, destination, input$}
        \State \Call {$\textit{add-transition}$}{$source, new, input$}
        \State $outbound \gets \{(i, w) \;|\; \exists w \in Q. (\delta(w, i) = destination)\}$
        \For {$(input, destination) \in outbound$}
          \State \Comment{Bounce back from the new state \\
            \hspace{6.7cm} to the states immediately \\
            \hspace{6.7cm} reachable from source state}
          \State \Call {$\textit{add-transition}$}{$new, destination, input$}
        \EndFor
      \EndFor
    \EndProcedure
  \end{algorithmic}
\end{algorithm}

Another way to go about this is to simply construct an automaton accepting all words of $Σ* \setminus \{w \;|\; \#(w) = 1\}$ (example given below), and to take a product of this newly constructed automaton with $A$. $B$ will accept the language of $A$ sans the words of length 1 because of the properties of the product of automata. Only the words accepted by both automata are accepted by the product, in particular, all words accepted by $A$ are accepted by $B$, unless they have length equal to 1. Conversely, whenever a word is accepted by $A$, it is also accepted by $B$, (because it is accepted by both original automata) and it is not accepted if it has length equal to 1 (because the constructed automata doesn’t accept such words by construction).

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick]

  \node[accepting,initial,state] (A)              {$q_a$};
  \node[state]                   (B) [right of=A] {$q_b$};
  \node[accepting,state]         (C) [right of=B] {$q_c$};

  \path (A) edge              node {$a \in \Sigma$} (B)
        (B) edge              node {$a \in \Sigma$} (C)
        (C) edge [loop right] node {$a \in \Sigma$} (C);
\end{tikzpicture}