Printer Friendly

Efficient solutions for the complement of [ww.sup.R] and the complement of ww.

1. Introduction

Formalisms describing language classes located between deterministic context free languages (CFL) and non deterministic context free languages have been intensively studied for many years. One of the motivations was to find families with acceptable computational complexity and sufficient expressiveness, as well as having natural characterizations by grammars and machine models. In what follows we prove that the languages [L.sub.1] and [L.sub.2] (defined below) are context free by designing non deterministic pushdown automaton that accepts them.

Let [logical not][L.sub.1] = {[ww.sup.R]/ w [member of] [{0, 1}.sup.*]} and [logical not][L.sub.2] ={ww / w [member of] [{0, 1}.sup.*]}. [logical not][L.sub.1] is a context free language and [logical not][L.sub.2] is a language of type 0 according to the Chomsky hierarchy. [logical not][L.sub.1] is known as the even length palindromes. According to the notation adopted, the language [L.sub.1] is the complement of the even length palindrome language, it is also known as the language of even length non palindromes. [L.sub.2] is the complement of the language [logical not][L.sub.2]. Palindromes are symmetric strings that read the same forward and backward, for example the string radar is a non even length palindrome, while the string elle is an even length palindrome. Formally, a non-empty string w is a palindrome if w = [w.sup.R] where [w.sup.R] denotes the string w reversed. It is convenient to distinguish between even length palindromes that are strings of the form [ww.sup.R] and odd length palindromes that are strings of the form [waw.sup.R], where a is a single alphabet symbol.

The paper is organized as follows. In the following sections we present some basic notions and definitions used in formal language theory. In chapter II we show that the complement of the language [ww.sup.R] is context free by designing a non deterministic finite pushdown automaton that accepts it. In chapter III we prove a similar result for the complement of the language ww. Finally we conclude our paper and point out some future directions of research.

1.1. Preliminaries

A word or string over an alphabet [SIGMA] can be any finite sequence of characters or symbols. The set of all words over an alphabet [SIGMA] is usually denoted by [[SIGMA].sup.*] (using the Kleene star notation, [1]). The length of a word is the number of symbols or letters it is composed of. For any alphabet there is only one word of length 0, the empty word, which is often denoted by [epsilon] or [lambda]. By concatenation one can combine two words to form a new word, whose length is the sum of the lengths of the original words. A language L is any finite subset of [[SIGMA].sup.*].

Unless stated otherwise we will use lower case letters (a, b, c) to denote input symbols, and upper case letters to denote stack symbols (X, Y, Z). Greek letters indicated strings of stack symbols. Finally u, v, w denote strings of input symbols.

Definition 01

The complement [logical not]L of a language L with respect to a given alphabet [SIGMA] consists of all the strings over the alphabet that do not belong to L. It is defined by [logical not]L = {x [member of] [[summation].sup.*]/x [not member of] L}.

Definition 02

A non deterministic pushdown automaton or NPDA is a 7-tuple M = (Q, [SIGMA], [??], [delta], [q.sub.0], [Z.sub.0], F) where:

Q is a set of finite states,

[SIGMA] is the input alphabet,

[??] is the stack alphabet which may include [SIGMA],

[delta] is the transition function,

[q.sub.0] [member of] Q is the initial state,

[Z.sub.0] [member of] [??] is the symbol at the bottom of the stack, which is used to test whether the stack is empty or not.

F [subset or equal to] Q is a set of final states.

The transition function [delta] for a NPDA has the form Q x ([summation] [union]{[lambda]}) x [??] [right arrow] finite subsets of Q x [[??].sup.*] where

[delta] is a function of three arguments. The first one is a state from Q, the second argument is either [lambda] or the current symbol from the input alphabet. The third argument is the current Y symbol on top of the stack. Thus we may write the transition function as:

[delta] (q, a, Z) = {([p.sub.1], [Y.sub.1]), ([p.sub.2], [Y.sub.2]), ..., ([p.sub.n], [Y.sub.n])}

When the input symbol is from [SIGMA], it is always consumed, that is the input head moves one step to the right. When the input symbol is set to [lambda] the input head does not move; this move is termed a [lambda] move. In the deterministic case, when the function [delta] is applied, the automaton moves to a new state q [member of] Q and pushes a new string of symbols [gamma] [member of] [[??].sup.*] onto the stack. Since we are dealing with a nondeterministic pushdown automaton, the result of applying [delta] is a finite set of (q, x) pairs. If we were to draw the automaton, each such pairwould be represented by a single arc. As with a finite state automaton we do not need to specify [delta] for every possible combination of arguments; when the transition function is not explicitly defined, it means that the machine enters a dead state and rejects [1,2].

Definition 03 NPDA moves

We distinguish two moves of the NPDA: a regular move when the input head is advanced, and a [lambda] move when the input head is not advanced.

i) The interpretation of:

[delta] (q, a, Z) = {([p.sub.1], [y.sub.1]), ([p.sub.2], [y.sub.1]), ..., ([p.sub.n], [y.sub.n])}

where q and [p.sub.i] are states; a an input symbol from [SIGMA], and Z a stack symbol from [??], is that the NPDA in state q with the input symbol a and Z the symbol on top of the stack, can for any i enter state [p.sub.i], replace the symbol Z by the string [Y.sub.i] and advance the input head one symbol to the right. We will adopt the usual convention that the leftmost symbol of [Y.sub.i] will be placed on top of the stack. Furthermore if:

* [absolute value of [Y.sub.i]] = 1 the top of the stack remains the same (we do not push or pop any symbol)

* [absolute value of [Y.sub.i]] = 0, that is [Y.sub.i] = [lambda] we pop a symbol from the stack, sometimes we write pop

* [absolute value of [Y.sub.i]] > 1 we push symbols on the stack

ii) The interpretation of:

[delta] (q, [lambda], R) = {([p.sub.1], [Y.sub.1] ([p.sub.2], [Y.sub.2]), ..., ([p.sub.n], [Y.sub.n])}

is that the NPDA in state q, independently of the input symbol being scanned, and with the symbol R on top of the stack, can enter state [p.sub.i], replace R by [Y.sub.i], for any i. In this case the input head is not advanced.

Definition 04

An instantaneous description (ID) of a pushdown automaton is a triplet (q, w, u), where

* q is the current state of the automaton,

* w is the unread part of the input string, and

* u is the stack contents (written as a string, with the leftmost symbol lying at the top of the stack).

Let the movement relation "[??]" indicates a move of the NPDA. It is related to the transition function [delta] as follows:

If [delta] (p, a, X) = (q, [gamma]) then (p, aW, X[alpha])[??] (q, W, [gamma][alpha])

Where W indicates the rest of the string following the symbol a, and [alpha] indicates the rest of the stack content underneath the symbol X. This notation says that in moving from state p to state q, the symbol a is consumed from the input string aW, and the string Xa on the stack (X is on the top of the stack) is replaced by the string [gamma]a.

(p, aW, X[alpha]) and (q, W, [gamma]a) are known as consecutive instantaneous descriptions and are often used to define the current configuration of the NPDA [2, 3].

In essence, a pushdown automaton is nondeterministic. It accepts the input string if there is a sequence of actions leading to the final state. There are two ways to depict non determinism in the flowchart: two transitions with the same label or a transition labeled with [lambda] (which does not consume an input symbol). All possibilities that do not have explicit transitions, have implicit transitions that go to an implicit reject state. Considering a computation of a pushdown automaton we call a single step nondeterministic if the automaton has more than one choice for its move. The branching of the step is defined to be the number of choices [4, 5].Most of the context-free languages differ in the amount of the resource (in this case, nondeterminism) that they require [6, 7].

Throughout the paper [lambda] denotes the empty word. For a string x, let [absolute value of x], x [i] and x [i, j] denote the length of x, the ith symbol of x and the factor x [i] ... x [j] respectively, where 0 < i [less than or equal to] j [less than or equal to] [absolute value of x]. Let [x.sup.R] denote the reverse of the word x, that is [x.sup.R] = x [n] x [n - 1] ... x [2] x [1] for [absolute value of x] = n. We assume throughout the paper that the special symbol [Z.sub.0] can only occur on the bottom of the pushdown automaton, and the input string terminates with the symbol $.

1.2. Accepting strings with a NPDA

We use the relation "[??]" to indicate a single move of the NPDA. We use the relation "[??]", the reflexive closure of the relation T" to indicate a sequence of zero or more moves.

If M = (Q, [SIGMA], [??], [delta], [q.sub.0], [Z.sub.0], F) is an NPDA, then the language accepted by M, L (M), is defined by L (M) = {w [member of] [[summation].sup.*]: ([q.sub.0], w, [Z.sub.0]) [[??].sup.*] (p, $, [Z.sub.0]), p [member of] F}.

This definition means that a string w is accepted if and only if starting from the start state [q.sub.0] and an empty stack (depicted by the symbol [Z.sub.0] on its top, we end up, after a sequence of moves, in a final state p after consuming entirely the input string. We assume that the input string terminates with the special symbol $, and [Z.sub.0] is the bottom of the stack. The symbol [Z.sub.0] is a convenient way to test for the empty stack condition, which means we are accepting by empty stack.

Acceptance by final state is the most common mode for acceptance; however proofs of basic theorems are often derived from acceptance by empty stack. Henceforth we will assume throughout this paper that acceptance is made by empty stack.

Some results on CFLs can be found in ([2, 3]): A context free language or CFL is a language generated by o context free grammar or accepted by a NPDA. A deterministic context free language (DCFL) is a language accepted by a deterministic pushdown automaton. Throughout the paper we prove that languages are context free by designing NPDA that accepts them. CFL are not closed under complement, we cannot just reverse final and non final states to find the complement. This does not work because it did not work for non deterministic finite state automaton (NDFA). CFL are closed under union, however DCFL are not closed under union. DCFL and CFL are not closed under intersection. In general deterministic machines are closed under complement. Two NPDAs are equivalent if they accept the same language.

1.3. Example of some transitions

For ease of understanding the most used transitions are explained in detail below:

1. [partial derivative] (p, a, R) = {(q, aR)} in state p, on input symbol a and R the top of the stack : move to state q and push a on top of the stack.

2. [partial derivative] (p, a, R) = {(q, R)} in state p, on input symbol a and R the top of the stack : move to state q and leave R on top of the stack (do not push a onto the stack).

3. [partial derivative] (p, a, R) = {(q, [lambda])} in state p, on input symbol a and R the top of the stack : pop (unstack the symbol R).

4. [partial derivative] (p, [lambda], R) = {(q, R)} this is a [lambda] move: the input head is not advanced and the top of the stack remains the same. All we do is move to a different state.

5. [partial derivative] (p, [lambda], _R) = {(q, R)} the anonymous variable "_" stands for any input symbol from [SIGMA] (Stack the input symbol, whatever it is)..

6. [partial derivative] (p, a, _) = {(q, a_)} the anonymous variable "_" stands for any stack symbol from [GAMMA].

7. [partial derivative] (p, -, [Z.sub.0]) = {(q, [Z.sub.0])} the stack is empty

8. [partial derivative] (p, $, -) = {(q, _)} the input is totally consumed

9. [partial derivative] (p, $, [Z.sub.0]) = {(q, [Z.sub.0])} the input is totally consumed and the stack is empty

In the following chapter we provide two solutions for the language [L.sub.1]: the first solution is simple and clear, the second solution is much more elegant and subtle. We first recall the grammar classification according to Chomsky.

1.4. The Chomsky Hierarchy of formal grammars

Let G = (V, T,P, S) be a formal grammar where V is the non terminal vocabulary, T is the terminal vocabulary, P is the set of the productions, and S is the starting symbol. We distinguish four types of grammars depending on the form of their productions ([1]).

Unrestricted Grammars: The languages defined by these grammars are accepted by Turing machines. They have rules of the form a [right arrow] b where [alpha] and [beta] are arbitrary strings over a vocabulary V and [alpha] # [epsilon].

Context-sensitive grammars: the languages defined by these grammars are accepted by linear bounded automata. They have rules of the form [alpha][right arrow][beta] where [absolute value of [alpha]] [less than or equal to] [absolute value of [beta]] where [alpha], [beta] [member of] [(V + T).sup.*], and a # [epsilon].

Context-free grammars: the languages defined by these grammars are accepted by push-down automata. They have rules of the form A [right arrow] [beta], where A [member of] V and [beta][member of] [(V + T).sup.*].

Regular grammars: the languages defined by these grammars are accepted by finite state automata. There are two kinds of regular grammars:

1. Right-linear with rules of the form A [right arrow] wB/w, where A, B [member of] V and w [member of] [T.sup.*].

2. Left-linear with rules of the form A [right arrow] wB/w.

2. Non Even Length Palindromes

Non deterministic solutions for context free languages have long proven difficult because the notion of non determinism in algorithm design is not easy to implement. However non deterministic approaches provided an elegant and subtle way to prove that languages are context free.

Recall that the language known as the non even palindromes is defined as the complement of the language {[ww.sup.R]/w [member of] {0, 1}*}, we will call this language [L.sub.1] In this section we prove that [L.sub.1] is a context free language. Precisely we construct a non deterministic pushdown automaton that accepts [L.sub.1].

Claim 01: The language [L.sub.1] is a context free language We prove the above statement by the construction of a non deterministic pushdown automaton that accepts the language. We begin with a naive solution and then proceed to a much better one. The first solution is given to make sure that the average reader understands the design of NPDA and also to get used with the notation.

2.1. A first solution for the language [L.sub.1]

Consider the following language: [logical not][L.sub.1] = {[ww.sup.R]/w [member of] [{0, 1}.sup.*]}. This is the set of strings in which each string begins with a sequence of one or more 0s or 1s and then immediately concludes with an identical but reversed sequence. In other words, [logical not][L.sub.1] is the set of symmetric even-length palindromes over the alphabet {0, 1}. Let us construct a NPDA [M.sub.1] which accepts [L.sub.1].

[M.sub.1] is defined by the set M = (Q, [summation], [??] [delta], [q.sub.0] [Z.sub.0], F)

where Q = {[q.sub.0], [q.sub.1], [q.sub.2], [q.sub.3], [q.sub.4], [q.sub.5], [q.sub.6]}, [summation] = [0, 1}, [??] = {[Z.sub.0], X, Y}, and F = {[q.sub.4], [q.sub.6]}

2.1.1 Initial part of the algorithm:

First of all we know that odd length strings belong to [L.sub.1].In this part all we have to do is to make sure that the input has an odd length to be accepted. From the start state [q.sub.0] we make a [lambda] move to state [q.sub.5]. From [q.sub.5] on any input symbol we move to state [q.sub.6], and then loop on state [q.sub.5] when reading the next input symbol. Thus the pushdown automaton behaves like a finite automaton and we accept if we end up in the final state [q.sub.6].

* [delta]([q.sub.0], [lambda], [Z.sub.0]) = {([q.sub.1], [Z.sub.0]), ([q.sub.5], [Z.sub.0]} make a [lambda] move either to state [q.sub.1] or to state [q.sub.5]

* [delta]([q.sub.5], -, [Z.sub.0]) = {([q.sub.6], [Z.sub.0])}

* [delta]([q.sub.6], -, [Z.sub.0]) = {([q.sub.5], [Z.sub.0])}

We move to state [q.sub.1] for the second part of the algorithm when the input has an even length.

2.1.2 Second part of the algorithm:

For the second part of the algorithm which is the main part of the problem we deal with even length strings which are not palindromes. The main idea is to look for mismatches non deterministically from the first half of the string w and the second half of the string [w.sup.R], specifically:

1. In state [q.sub.1] push a set of symbols on the stack (reading the symbol 0 push the symbol X, reading the symbol 1 push the symbol Y)

2. Guess that we have reached the middle of the string and move to state [q.sub.2]

3. In state [q.sub.2] match the rest of the symbols with the stack content (match 0 against X, and 1 against Y).

4. Find a mismatch on a 0 or a 1 and move to state [q.sub.3]

5. While in state [q.sub.3] pop everything out of the stack

6. When the input is totally consumed and the stack becomes empty, move to state [q.sub.4] accept and resume.

In state [q.sub.2], we make sure that the symbols we pushed earlier in state [q.sub.1] match the symbols we popped, which confirms the fact that the string is of even length. Since while reading the input symbol 0 (respectively 1) we pushed the symbol X (respectively Y) on top of the stack. A mismatch occurs in state [q.sub.2] only if the input symbol is 0 (respectively 1) and the symbol on top of the stack is Y (respectively X). We reach state [q.sub.3] if and only if we encounter a mismatch, which means that the input string is not of the form [ww.sup.R], thus the input string belongs to the set [L.sub.1].

2.1.3.. Transitions for M

Here are the transitions of the machine:

* [delta] ([q.sub.1], 0, [Z.sub.0]) = {([q.sub.1], X[Z.sub.0])} reading the first input symbol 0 push X.

* [delta] ([q.sub.1], 1, [Z.sub.0]) = {([q.sub.1], Y[Z.sub.0])| reading the first input symbol 1 push Y.

* [delta] ([q.sub.1], 0, T) = {([q.sub.1], XT)} reading the next input symbol 0 push A', the top of the stack is T = {X, Y}.

* [delta] ([q.sub.1], 1, T) = {([q.sub.1], YT)} reading the next input symbol 1 push Y, the top of the stack is T = {X, Y}.

* [delta] ([q.sub.1], [lambda], R) = {([q.sub.2], R)} At any time, guess that we have reached the middle of the string and move to state [q.sub.2]. This is a l move, the input head is not advanced and R = {X, Y}.

* [delta] ([q.sub.2], 0, X) = {([q.sub.2],pop)} match the input symbol 0 with the symbol X on the stack.

* [delta] ([q.sub.2], 1, Y) = {([q.sub.2], pop)} match the input symbol 1 with the symbol Y on the stack.

* [delta] ([q.sub.2], 0, Y)) = {([q.sub.3], pop)} guess a mismatch on the symbol 0 when encountering Y on top of the stack and enter state [q.sub.3].

* [delta] ([q.sub.2], 1, X) = {([q.sub.3], pop)} guess a mismatch on the symbol 1 when encountering X on top of the stack and enter state [q.sub.3]

* [delta] ([q.sub.3], -, -) = {([q.sub.3], pop)} pop everything out of the stack

* [delta] ([q.sub.3], $, [Z.sub.0]) = {([q.sub.4], Z0)} move to [q.sub.4] and accept

2.2 A More Efficient Solution for [L.sub.1]

Let us consider again the language [L.sub.1] the complement of the language [logical not][L.sub.1] = {[ww.sup.R]/w [member of] [{0, 1}.sup.*]}. In what follows we describe a more efficient solution for the even length non palindromes. In this version we do not need to remember the symbols, all we have to do is count the number of symbols. That is the stack is used as a counter. Specifically we push the symbol X either when reading 0 or 1. We say that two symbols x [i] and x [j] from the input string mismatch if they hold different values. Note that this notion of mismatch is slightly different from the one used in section II. A.

The main intuition justifying the conjecture that even length non palindromes are CFL is based on the following observation. Let us consider the string x = [ww.sup.R] = x [1] x [2] x [3] ... x [n - 1] x [n] x [n] x [n - 1] ... x [3] x [2] x [1].

We can easily note that the symbols x [i] and x [2n - i + 1] are identical for 1 [less than or equal to] i [less than or equal to] n. This tells us that the string cannot be a palindrome if the symbols at position i and position (2n - i + 1) mismatch. That means that all we have to do is make sure that there exits two symbols that mismatch for the string to be in [L.sub.1]. Let the mismatching symbols be x[i] and x (2n - i + 1), from left to right in the string. The number of symbols that precede x[i] is equal to the number of symbols that follow x (2n - i + 1), which is exactly (i - 1). Moreover all these symbols are identical. We will use the stack to make sure that this condition holds. The symbols that lie between x[i] and x (2n - i + 1) do not matter much since the mismatching symbols are non deterministically guessed..

The main idea is as follows: the mismatching symbols x [i] and x [2n - i + 1] are pointed by the double arrows in figure01. Let [A.sub.1] be the substring x [1, i - 1], [A.sub.2] the substring x [i + 1, 2n- i], and [A.sub.3] the substring x [2n - i + 2, 2n]. In zone [A.sub.1] we push the symbols onto the stack. In partA2 we just ignore the input, in part [A.sub.3] we pop the symbols making sure that they match what we have pushed in zone [A.sub.1].

In figure 01 the input string is represented by the rectangle. Substring [A.sub.1] lies before the first vertical double arrow on the left, substring [A.sub.2] lies between the two double arrows, and substring [A.sub.3] lies beyond the second double arrow on the right. The vertical double arrows indicate the two symbols that must mismatch. [A.sub.1] and [A.sub.3] have the same length. The main algorithm for the second solution is described below.

2.2.1 Algorithm for [L.sub.1]

a) Read the input symbols and push them onto the stack (push the symbol X either for 0 or 1).

b) At any time we non deterministically guess the symbol in the first part of the input string (w) that is going to mismatch a subsequent symbol in the second part of the string ([w.sup.R]). In state [q.sub.2] we remember the symbol 0, and in state [q.sub.3] we remember the symbol 1.

c) We remember this symbol and move across the input ignoring everything until we non deterministically guess the second symbol for a mismatch. From [q.sub.2] the mismatching symbol is 1, from state [q.sub.3] the mismatching symbol is 0.

d) From this point we make sure that the pushing at the start matches the popping at the end. Precisely the number of symbols (only Xs) pushed in part a) is equal to the symbols remaining on the stack. This means that the symbols that mismatch are legitimate mismatches as depicted in the figure 01 above.

This is a higher level of guessing, where we non deterministically check that we made the right guess for a mismatch. This solution avoids the main loops in the earlier version of the algorithm (section II.A) and is more subtle and elegant.

2.2.2..Transition function for [L.sub.1]

* [delta] ([q.sub.1], 0, [Z.sub.0]) = {([q.sub.1], X[Z.sub.0]), ([q.sub.2], [Z.sub.0])} while reading the first symbol 0 push X onto the stack or remember the symbol 0 as the mismatch and move to state [q.sub.2]

* [delta] ([q.sub.1], [Z.sub.0]) = {([q.sub.1], X[Z.sub.0]), ([q.sub.3], [Z.sub.0])} while reading the first symbol 1 push X onto the stack or remember the symbol 1 as the mismatch and move to state [q.sub.3]

* [delta] ([q.sub.1], 0, X) = {([q.sub.1], XX), ([q.sub.2], X)} while reading the next symbol 0 push X onto the stack or remember the symbol 0 as the mismatch and move to state [q.sub.2]

* [delta] ([q.sub.1], 1, X) = {([q.sub.1], XX), ([q.sub.3], X)} while reading the next symbol 1 push X onto the stack or remember the symbol 1 as the mismatch and move to state [q.sub.3]

* [delta] ([q.sub.2], 0, X) = {([q.sub.2], X)} while in state [q.sub.2] ignore the input symbol 0

* [delta] ([q.sub.2], 1, X) = {([q.sub.2], X), ([q.sub.4], X)} while in state [q.sub.2] ignore the input symbol 1 or guess that this is the mismatch symbol and move to state [q.sub.4]

* [delta] ([q.sub.3], 1, X) = {([q.sub.3], X)} while in state [q.sub.3] ignore the input symbol 1

* [delta] ([q.sub.3], 0, X) = {([q.sub.3], X), ([q.sub.4], X)} while in state [q.sub.3] ignore the input symbol 0 or guess this is the mismatch symbol and move to state [q.sub.4]

* [delta] ([q.sub.4], 0, X) = {{[q.sub.4], pop)} check and pop

* [delta] ([q.sub.4], 1. X) = {{[q.sub.4], pop)} check and pop

* [delta] ([q.sub.4], $, [Z.sub.0]) = {([q.sub.5], [Z.sub.0])} if the input is totally consumed and the stack is empty then accept and resume.

In state [q.sub.2] the mismatch is going to occur on a 1, since we remembered the symbol 0. In state [q.sub.3] the mismatch is going to occur on a 0, since we remembered the symbol 1. We reach state [q.sub.4] if and only if we encounter a mismatching symbol, which proves that the input string belongs to the language [L.sub.1]. The non deterministic technique is a powerful tool for the design of strategies when dealing with pushdown automaton.

Example of computations on the input 001110

The initial ID of the NPDA is: ([q.sub.1], 001110$, [Z.sub.0]). Each move is represented in a line and commented.

([q.sub.1], 001110$, [Z.sub.0]) read 0 push X

[??] ([q.sub.1], 01110$, X[Z.sub.0]) guess 0 as a future mismatch

[??] ([q.sub.2], 1110$, X[Z.sub.0]) ignore the symbol 1

[??] ([q.sub.2], 110$, X[Z.sub.0]) ignore the symbol 1

[??] ([q.sub.2], 10$, X[Z.sub.0]) guess 1 as the corresponding mismatching symbol

[??] ([q.sub.4], 0$, [Z.sub.0]) match X[Z.sub.0] with X

[??] ([q.sub.5], $, [Z.sub.0]) move to state [q.sub.5]

[??] ([q.sub.5], $, [Z.sub.0]) accept and resume

The input string 0101111010, which has the form [ww.sup.R], is not accepted wherever the two mismatching symbols may lie.

In the next chapter we design a NPDA for the language [L.sub.2]. To the best of our knowledge the solutions provided for [L.sub.1] and [L.sub.2] are new and have not been discussed in the literature.

3. The complement of [logical not][L.sub.2]

Let us now consider the complement of the language {ww/w [member of] [{0, 1}.sup.*]}, we are about to prove that this language, labeled [L.sub.2] is a context free language..

Claim 02: the language [L.sub.2] is a context free language.

Proof of Claim 02

To prove that the language [L.sub.2] is a CFL we design a NDPA that accepts the language. As before there are two aspects for strings in [L.sub.2], first of all odd length words are in L2. We can take care of this situation by designing a finite automaton that recognizes odd length strings. In what follows we only consider even length words. Let the string x = ww = x [1] x [2] x [3] ... x [n - 1] x [n] x [1] x [2] x [3] ... x [n - 1] x [n]. The matching symbols x[i] and x [n + i] are pointed out by the vertical double arrows in figure02. Let [A.sub.1] be the substring x [1, i - 1], [A.sub.2] the substring x [i + 1, n + i + 1], and [A.sub.3] the substring x [n + i + 2, 2n].

We notice that the identical symbols x [i] and x [n + i] from the first part of the string and the second half are separated by exactly n-1 symbols. Moreover the number of symbols that lie before the first x[i] that is i - 1, when added to the number of symbols that lie after the second x [n + i], that is n - i, equals n - 1. This suggests that a string is in [L.sub.2] if and only if the two mismatching symbols are separated by half the length of the total string. This is made clear in the figure 02 below where the vertical double arrows show the two mismatching symbols.

This tells us that we have to make sure that the two mismatching symbols are separated by half of the total string length. Let us push Xs for a while, say [n.sub.1]. Decide that the next input symbol is the mismatching symbol, remember it and start to pop symbols from the stack, say [n.sub.2]. If the stack becomes empty, start pushing again Xs onto the stack, say [n.sub.3]. Then arbitrarily guess the next input symbol is the corresponding mismatching symbol. Now we pop everything out of the stack, say [n.sub.4] symbols. At this point when the stack empties then we know that the set consisting of the popping of the first set ([n.sub.2]) and the pushing of the second set ([n.sub.3]) is the same as the pushing of the first set ([n.sub.1]) and the popping of the second set ([n.sub.4]), that they are equal. That is [n.sub.2] + [n.sub.3] = [n.sub.1] + [n.sub.4], which proves that the two mismatching symbols are legitimate and separated by half of the total string length.

The two mismatching symbols pictured by the vertical double arrows in figure 02 are separated by half the length of the total string. This is a neat solution that requires a single counter. The whole idea which is a bit subtle is to make a guess and then later non deterministically check that our guess was the right one. In figure 02, as before, substring [A.sub.1] lies before the first vertical double arrow on the left, substring [A.sub.2] lies between the two vertical double arrows, and substring [A.sub.3] lies beyond the second double arrow on the right. Then the length of the string [A.sub.1] added to the length of the string [A.sub.3] equals the length of the string [A.sub.2]. If the length of the input string ww is 2n then [absolute value of [A.sub.1]] + [absolute value of [A.sub.3]] = [absolute value of [A.sub.2]] = n.

In figure 02 the input string is represented as a rectangle. The vertical double arrows show where the two mismatching symbols lie. They are separated by half the length of the total string depicted by the horizontal double arrow. We describe the algorithm in the next section.

3.1. Algorithm for [L.sub.2]

a) Push a bunch of symbols on the stack and arbitrarily guess that you are choosing to look at a specific symbol

b) Pop those symbols off the stack, if the stack becomes empty start pushing the symbols again non deterministically guessing when to make a mismatch. When the stack becomes empty we push a different symbol onto the stack.

c) Find a mismatch, at that point pop the symbols that you have off the stack

d) If the input string is entirely consumed and the stack is empty then we know here that the set consisting of the popping of the first set and the pushing of the second set was the same as the pushing of the first set and the popping of the second set, that they are equal. That means that the middle section [A.sub.2] is half the length of the total input string length.

3.2. Transition function for [L.sub.2]

The NPDAM, is defined by the set M = (O, [summation], [??], [delta], [q.sub.1], [Z.sub.0] F) where Q = {[q.sub.1], [q.sub.2], [q.sub.3], [q.sub.4], [q.sub.5], [q.sub.6], [q.sub.7]}, [summation] = (0, 1}, [??] = {[Z.sub.0], X Y}, and F = {[q.sub.7]}

1. [delta] ([q.sub.1], 0, T) = {([q.sub.1], XT), ([q.sub.2], T)} when reading the symbol 0 push X onto the stack or guess the symbol 0 as a mismatch and move to [q.sub.2], T = {[Z.sub.0], X}

2. [delta] ([g.sub.1], 1, T) = {([q.sub.1], XT), ([q.sub.3], T)} when reading the symbol 1 push X onto the stack or guess the symbol 1 as a mismatch and move to [q.sub.3], T = {[Z.sub.0], X}

3. [delta]([q.sub.2], 0, X) = {([q.sub.2], pop)}

4. [delta] ([q.sub.2], 1, X) = {([q.sub.2], pop)}

5. [delta]([q.sub.2], [lambda], [Z.sub.0]) = {([q.sub.4], [Z.sub.0])}the stack is empty, move to state [q.sub.4]

6. [delta]([q.sub.3], 0, X) = {([q.sub.3], pop)}

7. [delta]([q.sub.3], 1, X) = {([q.sub.3], pop)}

8. [delta]([q.sub.3], [lambda], [Z.sub.0]) = {([q.sub.5], [Z.sub.0])}the stack is empty, move to state [q.sub.5]

9. [delta] ([q.sub.4], 0, T) = {([q.sub.4], YT)} when reading the symbol 0 pop again Ys onto the stack, T = {[Z.sub.0], X}

10. [delta]([q.sub.4], 1, T) = {([q.sub.4], YT), ([q.sub.6], T)} when reading the symbol 1 pop again Ys onto the stack or guess the mismatch and move to state [q.sub.6], T = {[Z.sub.0], X}

11. [delta]([q.sub.1], T) = {([q.sub.5], YT)} when reading the symbol 1 pop again Ys onto the stack, T = {[Z.sub.0], Y}

12. [delta]([q.sub.5], 0, T) = {([q.sub.5], YT), ([q.sub.6], T)} when reading the symbol 0 pop again Ys onto the stack or guess the mismatch and move to state [q.sub.6], T = {[Z.sub.0], X}

13. [delta] ([q.sub.6], 0, Y) = {([q.sub.6], pop)} pop the Ys

14. [delta] ([q.sub.6], 1, Y) = {{[q.sub.6], pop)} pop the Ys

15. [delta] ([q.sub.6], $, [Z.sub.0]) = {([q.sub.7], [Z.sub.0])} the input is entirely consumed and the stack is empty then enter the final state [q.sub.7] and accept

If we assume that the amount of non determinism that a pushdown automaton requires to recognize an input string can be measured by the minimum number of guesses that it must make to accept the string then the solution we provide is efficient as we only make two (2) guesses ([4]).

3.3 Some Input computations

Here are some computations for the input 001011

The initial ID is ([q.sub.1], 001011$, [Z.sub.0])

[??] ([q.sub.1], 001011$, [Z.sub.0]) read 0 push X

[??] ([q.sub.1], 01011$, X[Z.sub.0]) guess 0 as the mismatch

[??] ([q.sub.2], 1011$, X[Z.sub.0]) pop

[??] ([q.sub.2], 011$, [Z.sub.0]) stack empty move to [q.sub.4]

[??] ([q.sub.4], 011$, [Z.sub.0]) push Y

[??] ([q.sub.4], 11$, Y[Z.sub.0]) guess 1 as the second mismatch and move to [q.sub.6]

[??] ([q.sub.6], 1$, Y[Z.sub.0]) pop

[??] ([q.sub.6], $, [Z.sub.0]) stack is empty move to [q.sub.7]

[??] ([q.sub.7], $, [Z.sub.0]) accept and resume

The mismaching symbols occur in the second and the fifth symbol. Here are some computations for the input 001000

([q.sub.1], 001000$, [Z.sub.0]) [??] ([q.sub.1], 1000$, XX[Z.sub.0]) [??] ([q.sub.3], 000$, XX[Z.sub.0]) [??] ([q.sub.3], 0$, [Z.sub.0]) [??] ([q.sub.5], 0$, [Z.sub.0]) [??] ([q.sub.6], $, [Z.sub.0]) [??] ([q.sub.7], $, [Z.sub.0])

The mismaching symbols occur in the third and the sixth symbol. If we try the string 01100110, it is clear that it is impossible to find two symbols to mismatch that are separated by half the string length, because this example is of the form ww, so it is rejected.

The main results of this paper are that the complement of the language [L.sub.1] = {[ww.sup.R]/w [member of] [{0, 1}.sup.*]} and the complement of the type 0 language [L.sub.2] = {ww/w [member of] [{0, 1}.sup.*]} are context free. We have shown these results by designing non deterministic pushdown automaton that accept these languages.

4. Conclusion

In this paper we have proved that the complement of the language [L.sub.1] = {[ww.sup.R]/w [member of] [{0, 1}.sup.*]} and the complement of the language [L.sub.2] = {ww/w [member of] [{0, 1}.sup.*]} are context free by designing non deterministic pushdown automatons that recognize these languages. The solutions provided are elegant and show that non determinism is a powerful tool for designing strategies to solve hard problems. Both languages can be characterized by the presence of two input symbols that mismatch. The main feature of the procedures is to determine the position of the symbols that have to mismatch in the input string. At some point we make a guess and then non deterministically prove that our guess was legitimate. The NPDA for the language [L.sub.2] uses the stack only as a counter; the value of the input symbol (0 or 1) does not matter. To the best of our knowledge the solutions provided are state of the art and have not been published in the literature.

Future directions of research might deal with the refinement of the non determinism measure, in other words how to reduce the branching factor (non deterministic moves) in the design of pushdown machines. It is also important to consider the relation between complexity measures, in terms of the size of input strings, and non deterministic moves when designing efficient algorithms.

Received: 18 July 2014, Revised 3 September 2014, Accepted 12 September 2014

References

[1.] Hopcroft, J., Ullman, J. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

[2.] Harrison, M. (1978). Introduction to Formal Language Theory. Addison-Wesley, Reading, MA.

[3.] Drobot, V. (1989). Formal Languages and Automata Theory. Computer Science Press, Rockville, MD.

[4.] Goldstine, J., Leung, H., Wotschke, D., (2005). Measuring nondeterminism in pushdown automata, Journal of Computer and System Sciences 71.440-466

[5.] Kutrib M Martin., Malcher, A. (2007). Context-dependent nondeterminism for pushdown automata. Theoretical Computer Science 376. 101-111

[6.] Jiang, T., Salomaa, A., Salomaa, K., Yu, S. (1995). Decision problems for patterns. Journal of Computer and System Sciences. 50 (1) 53-63.

[7.] Kutrib. M., Malcher. A., Werlein, L. (2009). Regulated nondeterminism in pushdown automata. Theoretical Computer Science 410. 3447-3460

Allaoua Refoufi

Computer Science Department University of Setif Algeria

allaoua.refoufi@univ-setif.dz

Biography

The author is currently a Professor in computer science at the University of Setif, Algeria. He graduated from the University of Colorado at Boulder, USA (Master of Sciences in 1980) and from the University of Sheffield, United Kingdom (PhD in Artificial Intelligence in 1990). His areas of research includes formal language theory, natural language processing and semantic web technologies. The author may be reached at allaoua.refoufi@univ-setif.dz
COPYRIGHT 2014 Digital Information Research Foundation
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Refoufi, Allaoua
Publication:Journal of Digital Information Management
Article Type:Report
Date:Dec 1, 2014
Words:7174
Previous Article:Weighting parameters to improve IHS transformation in data fusion of THEOS imagery.
Next Article:The evaluations of Thai poetry translator to English with prosody keeping.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |