Polimi CS - Notes

1 - Languages

10 min read

  • formal languages
  • formal models
  • formal model

Definition

A formal model is a mathematical representation of a physical system, which enables rigorous analysis of its properties and behaviors.

By utilizing formal models, we can achieve the following objectives:

  1. Problem Formalization: Transform a real-world problem into a mathematical framework.
  2. Problem Solving: Analyze and solve the formalized problem using mathematical techniques.
  3. Result Interpretation: Understand and evaluate the outcomes, and assess the implications of design decisions.

A model is deemed adequate if the results it yields align with the desired properties of the physical system, within acceptable error margins. It is considered useful if it simplifies the resolution of the original problem compared to direct analysis of the physical system.

The software engineering process typically encompasses the following main phases:

  1. Requirement Analysis: This phase involves identifying and documenting the requirements for the software, resulting in a specification document. Requirements can be expressed in natural language, feature lists, or use case scenarios.
  2. Design: In this stage, developers create a comprehensive plan for the software architecture. This includes detailing the system’s structure through class diagrams or Unified Modeling Language (UML) diagrams.
  3. Implementation: This is the coding phase, where the designed specifications are translated into a working software product.

While the first two phases often utilize natural or semi-formal languages, the adoption of formal languages and models is gaining traction, particularly in requirements and design documentation. This trend enhances the reliability and flexibility of the development process and enables the use of automated tools for generating design and code.

Formal Languages and Models

The formal models employed in Computer Science can be broadly categorized into two types:

  • Discrete Models: These models operate with discrete elements, such as bits and bytes, and are suitable for systems where states can be distinctly separated.
  • Continuous Models: These models employ real numbers and continuous functions, which are used in scenarios where data can change fluidly over time.

Formal models can be further classified into two primary categories:

  1. Operational Models: These models are based on the concepts of state and the mechanisms for representing their evolution over time. They are particularly useful in depicting the dynamic behavior of a system. For example, operational models are frequently applied in algorithm design and simulation of system processes.
  2. Descriptive Models: These models focus on expressing the properties of the system rather than detailing its time-dependent evolution. They rely on logical relationships and are often more abstract. Descriptive models are useful for formal verification and validation of system properties.

Sorting algorithms

Consider the sorting of a sequence of numbers:

  • Operational Definition of Sorting:
    1. Identify the minimum element and place it in the first position.
    2. Identify the minimum element from the remaining elements and place it in the second position.
    3. Repeat this process until the sequence is fully sorted.
  • Descriptive Definition of Sorting: A sorted sequence can be defined as a permutation of the original sequence such that for every index , .

While the boundaries between operational and descriptive models can sometimes blur (especially in grammars, which may combine aspects of both) the classification remains instrumental. It aligns closely with the differing approaches employed when analyzing and reasoning about systems.

Language

Definition

In computer science and linguistics, a language can be defined as a structured collection of strings.

This definition is broad and applies universally across various domains. Languages can encompass:

  • Natural Languages: These are languages used for human communication, such as English, Spanish, and Mandarin.
  • Artificial Languages: This category includes constructed languages like programming languages (e.g., Python, Java) that are specifically designed for instructing computers.
  • Graphics: Visual languages, such as graphical symbols or diagrams, convey information without the use of traditional text.
  • Music: Notations and compositions that represent musical sounds can be considered a form of language.
  • Multimedia: Combinations of text, audio, graphics, and video that communicate information effectively.

A language consists of an alphabet (or vocabulary) and a set of strings formed from that alphabet.

Definitions

Alphabet (or Vocabulary) is a finite collection of symbols from which strings are constructed. Examples include:

  • The English alphabet:
  • Binary digits:
  • Musical notes:
  • ASCII character set, which includes a variety of characters used in text representation.

Definition

String (over an Alphabet ): A string is defined as an ordered, finite sequence of elements drawn from the alphabet , allowing for repetitions. Examples of strings include:

  • Individual characters:
  • Repeated characters:
  • Words and phrases:

The length of a string is quantified as the number of elements it contains. For example, the length of the string is , and the length of the string is . The null string (or empty string), denoted by , has a length of .

A crucial concept in formal language theory is the set of all possible strings over an alphabet , represented as called free monoid. This set is defined, from the alphabet , as:

This set is infinite and includes every possible combination of strings formed from the alphabet, including the empty string .

One of the most significant operations that can be performed on strings is concatenation. The concatenation of two strings and is expressed as , resulting in a new string formed by appending to . This operation exhibits the following properties:

  • Associativity:
  • Non-commutativity:
  • Identity Element: The empty string serves as the identity element for concatenation, satisfying:

Example

For example, if we let and , then the concatenation results in:

The set , with the concatenation operation, forms a mathematical structure known as a monoid. A monoid is characterized by:

  • An associative binary operation (in this case, concatenation).
  • An identity element (the empty string ).

Definition

In formal terms, a language is defined as a subset of the free monoid over the alphabet . This can be expressed as:

Example

An example of a language is the C programming language, defined as the set of all syntactically correct strings that can be formed from the monoid of ASCII characters:

This means that any valid string that adheres to the syntax rules of the C language is included in the language set .

Operations on Languages

Since a language is defined as a set of strings, various set-theoretic operations can be applied to it. These operations include union (), intersection (), difference () (which refers to the elements in the first set that are not in the second set) and complement (), defined as , where is the set of all possible strings over the alphabet and is the language.

Example

The complement of the English language is the set of all strings that do not conform to the syntactic and grammatical rules of English. This includes random sequences of letters, symbols, or words that violate its structural rules.

Languages, viewed as sets of strings, can also undergo specialized operations such as concatenation, raising to a power, and closure operations like positive closure.

Concatenation of Languages

Given two languages and , the concatenation of these two languages is the set of all strings formed by concatenating a string from with a string from . Formally, this is defined as:

Concatenation combines two strings sequentially, one from each language.

Example

For example, let and . The concatenation of these two languages results in strings like , , , and so on. Both languages contain the empty string , meaning the concatenation can also produce strings from either language individually. However, a string like is not part of the concatenation because does not belong to the first language, and does not belong to the second.

Important Properties of Concatenation

  • The empty string acts as the identity element for concatenation, meaning that concatenating the empty string with any language results in the language itself:
  • The empty set is the absorbing element for concatenation, meaning concatenating any language with the empty set yields the empty set :

The set contains the empty string as an element, while is a completely empty set with no elements.

Power of a Language

Definition

The power of a language is the set of all possible strings generated by concatenating zero or more strings from . It is denoted as , where:

This set includes all concatenations of strings from , starting from the zero-length string (which is the empty string).

Example

For example, given , the power (the set of strings formed by concatenating two elements from ) would include:

The Kleene star () is used to describe this concept, where includes all possible repetitions of elements from .

Positive Closure

Definition

The positive closure of a language , denoted as , is similar to , except it excludes the empty string. In other words, it is the set of all strings obtained by concatenating one or more strings from :

For instance, if , then:

Here, includes all strings from except the empty string.

Translation

In computer science and mathematics, a language can serve as a medium for expressing a wide range of problems, such as messages, programs, or mathematical formulations. Since every string can be represented in binary, any problem expressed in a language can be converted into a problem of determining inclusion in a set of natural numbers.

A translation is a function that transforms strings from one language into strings of another language. This transformation can modify the structure of strings according to specific rules or objectives.

Definition

A translation is a function that maps each string in language to a corresponding string in language .

Examples of Translation Functions

  1. Doubling a Character: Suppose we want to double every occurrence of the character “1” in a binary string. A translation function can be defined to perform this transformation. For example, applying to the string “0010110” results in:

  2. Character Substitution: Another example of translation is swapping characters. A translation function could swap all instances of “a” with “b” and vice versa. Applying to the string “abbbaa” would result in:

Translation functions play a critical role in various domains, including:

  • File Compression: Translation can be used to encode data more efficiently by transforming repetitive or redundant patterns into more compact representations.
  • Error-Correcting Protocols: In communication systems, translations can be applied to detect and correct errors during transmission.
  • Computer Language Compilation: Translating high-level programming languages (such as C++ or Python) into low-level machine code is a crucial aspect of software development.
  • Natural Language Translation: In linguistic applications, translations allow us to convert text from one natural language (e.g., English) to another (e.g., Spanish).

Backlinks

Graph View