Language Structures in Cellular Automata

Language Structures in Cellular Automata

Eleonora Bilotta (University of Calabria, Italy) and Pietro Pantano (University of Calabria, Italy)
DOI: 10.4018/978-1-61520-787-9.ch009

Abstract

The ingenuity of nature and the power of DNA have generated an infinite range of languages - including human language. The existence of these languages inspires us to design artificial cognitive systems whose dynamic interaction with the environment is grounded, at least to some extent, on the same basic laws. Modern scientific knowledge provides us with new opportunities to investigate and understand the logic underlying biological life. We can then use this logic to derive design principles and computational models for artificial systems. The technologies we apply in these studies provide us with new insights into the complexity of the processes underlying the evolutionary success of modern species. We have yet to fully penetrate the mysteries of these natural languages. Nonetheless, the literature suggests (Chomsky, 1957; Aronof & Rees-Miller, 2003; Bilotta & Pantano, 2006) that while the superficial features of different languages depend on different physical supports and different mechanisms, their deep structures share common rules. These constitute linguistic universals, organized at different levels of complexity, where each level has its own rules of composition. At all levels, we can consider these rules as “production rules” or even as rules of reproduction.
Chapter Preview
Top

Introduction

The ingenuity of nature and the power of DNA have generated an infinite range of languages - including human language. The existence of these languages inspires us to design artificial cognitive systems whose dynamic interaction with the environment is grounded, at least to some extent, on the same basic laws. Modern scientific knowledge provides us with new opportunities to investigate and understand the logic underlying biological life. We can then use this logic to derive design principles and computational models for artificial systems. The technologies we apply in these studies provide us with new insights into the complexity of the processes underlying the evolutionary success of modern species. We have yet to fully penetrate the mysteries of these natural languages. Nonetheless, the literature suggests (Chomsky, 1957; Aronof & Rees-Miller, 2003; Bilotta & Pantano, 2006) that while the superficial features of different languages depend on different physical supports and different mechanisms, their deep structures share common rules. These constitute linguistic universals, organized at different levels of complexity, where each level has its own rules of composition. At all levels, we can consider these rules as “production rules” or even as rules of reproduction.

The use of formal languages to investigate CAs is not itself a novelty. (Minsky, 1967, Hopcroft, et al., 2007). In nearly all cases, the formal language provides an abstract representation of the system, based on a similar set of elements. Usually it is defined by a finite set of strings, constructed from a finite alphabet of symbols. Like a natural language (Chomsky, 2000), a formal language consists of the following elements:

  • 1.

    Symbols are abstract entities with no intrinsic meaning; they are often said to be “non-interpreted”.

  • 2.

    An alphabet is a finite set of symbols. Alphabets are often represented with the Greek character Σ. Other letters can also be used. The formula B = (0, 1) states that B is an alphabet consisting of two symbols, “0” and “1”. The formula C = (a, b, c) states that C is another alphabet made up of 3 symbols “a”, “b”, “c”. Punctuations marks and spaces are considered as symbols belonging to the alphabet. At times, descriptions of the alphabet use them as metasymbols.

  • 3.

    Words are finite sequences of symbols belonging to the alphabet. Thus, “001010” and “110” are words constructed from alphabet B; “caaabbb” e “ab” are words built from alphabet C. The beginning and end of a string are often shown with vertical bars. The length of the string is the number of characters between the bars. For example “|0011101|= 7”; “|aaabbb|= 6”. Null strings contain no characters and have a length of 0. These strings are usually shown by the Greek character “Ε”.

  • 4.

    A grammar is an abstract structure providing a precise representation of the formal language. This consists of a system of rules providing a mathematical representation of a (usually infinite) set of finite sequences of symbols (strings) constructed from an alphabet which is also finite. There are two kinds of formal grammar. A generative grammar consists of a system of rules with the ability to generate all possible strings belonging to a given language. It is a computational system in which an algorithm generates language strings. The rules make it possible to iteratively rewrite strings, beginning with a pre-defined initial symbol. Generative grammars are modeled on the way a language is written. By contrast, an analytical grammar is a system of rules that starts with an arbitrary input string, and applies an algorithm to the string, determining a series of outputs. When these outputs are combined using Boolean operators they produce a Yes/No response, determining whether the string belongs to the language described by the grammar. An analytical grammar is a language parser. The first author to formalize generative grammars was Noam Chomsky (Chomsky, 1957; 1980), who proposed a taxonomy of grammars, known as the “Chomsky hierarchy”. The grammars identified by Chomsky include context-free grammars and regular grammars. These respectively determine context-free languages and regular languages. The difference is that context-free grammars have a broader range of production rules and can generate more formal languages than regular grammars.

Complete Chapter List

Search this Book:
Reset