Formal languages

• Abstract syntax tree
  Abstract syntax tree
  In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
  
  
• Backus-Naur form
• Categorial grammar
  Categorial grammar
  Categorial grammar is a term used for a family of formalisms in natural language syntax motivated by the principle of compositionality and organized according to the view that syntactic constituents should generally combine as functions or according to a function-argument relationship...
  
  
• Chomsky hierarchy
  Chomsky hierarchy
  Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
  
  
• Concatenation
  Concatenation
  In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
  
  
• Context-free grammar
  Context-free grammar
  In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
  
  
• Context-sensitive grammar
  Context-sensitive grammar
  A context-sensitive grammar is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols...
  
  
• Context-sensitive language
  Context-sensitive language
  In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
  
  
• Decidable language
• ECLR-attributed grammar
  ECLR-attributed grammar
  ECLR-attributed grammars are a special type of attribute grammars. They are a variant of LR-attributed grammars where an equivalence relation on inherited attributes is used to optimize attribute evaluation. EC stands for equivalence class. Rie is based on ECLR-attributed grammars...
  
  
• Finite language
• Formal grammar
  Formal grammar
  A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
  
  
• Formal language
  Formal language
  A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
  
  
• Formal system
  Formal system
  In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
  
  
• Generalized star height problem
  Generalized star height problem
  The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they...
  
  
• Kleene algebra
  Kleene algebra
  In mathematics, a Kleene algebra is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan's laws , additionally satisfying the inequality x∧−x ≤ y∨−y. Kleene algebras are subclasses of Ockham algebras...
  
  
• Kleene star
  Kleene star
  In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
  
  
• L-attributed grammar
  L-attributed grammar
  L-attributed grammars are a special type of attribute grammars. They allow the attributes to be evaluated in one left-to-right traversal of the abstract syntax tree. As a result, attribute evaluation in L-attributed grammars can be incorporated conveniently in top-down parsing.Many programming...
  
  
• LR-attributed grammar
  LR-attributed grammar
  LR-attributed grammars are a special type of attribute grammars. They allow the attributes to be evaluated on LR parsing. As a result, attribute evaluation in LR-attributed grammars can be incorporated conveniently in bottom-up parsing. zyacc is based on LR-attributed grammars...
  
  
• Myhill-Nerode theorem
• Parsing expression grammar
  Parsing expression grammar
  A parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language...
  
  
• Prefix grammar
  Prefix grammar
  In computer science, a prefix grammar is a type of string rewriting system, consisting of a set of string rewriting rules, and similar to a formal grammar or a semi-Thue system. What is specific about prefix grammars is not the shape of their rules, but the way in which they are applied: only...
  
  
• Pumping lemma
  Pumping lemma
  In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of...
  
  
• Recursively enumerable language
  Recursively enumerable language
  In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
  
  
• Regular expression
  Regular expression
  In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
  
  
• Regular grammar
  Regular grammar
  In theoretical computer science, a regular grammar is a formal grammar that describes a regular language.- Strictly regular grammars :A right regular grammar is a formal grammar such that all the production rules in P are of one of the following forms:# B → a - where B is a non-terminal in N and...
  
  
• Regular language
  Regular language
  In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
  
  
• S-attributed grammar
  S-attributed grammar
  S-Attributed Grammars are a class of attribute grammars characterized by having no inherited attributes, but only synthesized attributes. Inherited attributes, which must be passed down from parent nodes to children nodes of the abstract syntax tree during the semantic analysis of the parsing...
  
  
• Star height
  Star height
  In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexityof regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression....
  
  
• Star height problem
  Star height problem
  The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars...
  
  
• Syntactic monoid
  Syntactic monoid
  In mathematics and computer science, the syntactic monoid M of a formal language L is the smallest monoid that recognizes the language L.-Syntactic quotient:...
  
  
• Syntax (logic)
  Syntax (logic)
  In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them...
  
  
• Tree-adjoining grammar
  Tree-adjoining grammar
  Tree-adjoining grammar is a grammar formalism defined by Aravind Joshi. Tree-adjoining grammars are somewhat similar to context-free grammars, but the elementary unit of rewriting is the tree rather than the symbol...
  
  

Literal strings

• Anagram
  Anagram
  An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse, A decimal point = I'm a dot in place, Tom Marvolo Riddle = I am Lord Voldemort. Someone who...
  
  
• Case sensitivity
  Case sensitivity
  Text sometimes exhibits case sensitivity; that is, words can differ in meaning based on differing use of uppercase and lowercase letters. Words with capital letters do not always have the same meaning when written with lowercase letters....
  
  
• Infinite monkey theorem
  Infinite monkey theorem
  The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare....
  
  
• Lexical analysis
  Lexical analysis
  In computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner...
  
  
  • Lexeme
    Lexeme
    A lexeme is an abstract unit of morphological analysis in linguistics, that roughly corresponds to a set of forms taken by a single word. For example, in the English language, run, runs, ran and running are forms of the same lexeme, conventionally written as RUN...
    
    
  • Lexicography
    Lexicography
    Lexicography is divided into two related disciplines:*Practical lexicography is the art or craft of compiling, writing and editing dictionaries....
    
    
  • Lexicon
    Lexicon
    In linguistics, the lexicon of a language is its vocabulary, including its words and expressions. A lexicon is also a synonym of the word thesaurus. More formally, it is a language's inventory of lexemes. Coined in English 1603, the word "lexicon" derives from the Greek "λεξικόν" , neut...
    
    
• Lipogram
  Lipogram
  A lipogram is a kind of constrained writing or word game consisting of writing paragraphs or longer works in which a particular letter or group of letters is avoided — usually a common vowel, and frequently "E", the most common letter in the English language.Writing a lipogram is a trivial task...
  
  
• The Library of Babel
  The Library of Babel
  "The Library of Babel" is a short story by Argentine author and librarian Jorge Luis Borges , conceiving of a universe in the form of a vast library containing all possible 410-page books of a certain format....
  
  
• Palindrome
  Palindrome
  A palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers....
  
  
• Pangram
  Pangram
  A pangram , or holoalphabetic sentence, is a sentence using every letter of the alphabet at least once. Pangrams have been used to display typefaces, test equipment, and develop skills in handwriting, calligraphy, and keyboarding...
  
  
• Sequence alignment
  Sequence alignment
  In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. Aligned sequences of nucleotide or amino acid residues are...
  
  

Classical cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

• Atbash cipher
• Autokey cipher
  Autokey cipher
  An autokey cipher is a cipher which incorporates the message into the key. There are two forms of autokey cipher: key autokey and text autokey ciphers. A key-autokey cipher uses previous members of the keystream to determine the next element in the keystream...
  
  
• Bazeries cylinder
• Bible code
  Bible code
  The Bible code , also known as the Torah code, is a purported set of secret messages encoded within the text Hebrew Bible and describing prophesies and other guidance regarding the future. This hidden code has been described as a method by which specific letters from the text can be selected to...
  
  
• Bifid cipher
  Bifid cipher
  In classical cryptography, the bifid cipher is a cipher which combines the Polybius square with transposition, and uses fractionation to achieve diffusion...
  
  
• Caesar cipher
  Caesar cipher
  In cryptography, a Caesar cipher, also known as a Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number...
  
  
• Cardan grille
  Cardan grille
  -History:In 1550, Girolamo Cardano , known in French as Jérôme Cardan, proposed a simple grid for writing hidden messages. He intended to cloak his messages inside an ordinary letter so that the whole would not appear to be a cipher at all....
  
  
• Enigma machine
  Enigma machine
  An Enigma machine is any of a family of related electro-mechanical rotor cipher machines used for the encryption and decryption of secret messages. Enigma was invented by German engineer Arthur Scherbius at the end of World War I...
  
  
• Frequency analysis
  Frequency analysis
  In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers....
  
  
• Index of coincidence
  Index of coincidence
  In cryptography, coincidence counting is the technique of putting two texts side-by-side and counting the number of times that identical letters appear in the same position in both texts...
  
  
• Playfair cipher
  Playfair cipher
  The Playfair cipher or Playfair square is a manual symmetric encryption technique and was the first literal digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair who promoted the use of the cipher.The technique encrypts pairs of...
  
  
• Polyalphabetic substitution
• Polybius square
  Polybius square
  In cryptography, the Polybius square, also known as the Polybius checkerboard, is a device invented by the Ancient Greek historian and scholar Polybius, described in , for fractionating plaintext characters so that they can be represented by a smaller set of symbols.-Basic form :The original square...
  
  
• ROT13
  ROT13
  ROT13 is a simple substitution cipher used in online forums as a means of hiding spoilers, punchlines, puzzle solutions, and offensive materials from the casual glance. ROT13 has been described as the "Usenet equivalent of a magazine printing the answer to a quiz upside down"...
  
  , ROT47
• Scytale
  Scytale
  In cryptography, a scytale is a tool used to perform a transposition cipher, consisting of a cylinder with a strip of parchment wound around it on which is written a message...
  
  
• Steganography
  Steganography
  Steganography is the art and science of writing hidden messages in such a way that no one, apart from the sender and intended recipient, suspects the existence of the message, a form of security through obscurity...
  
  
• Substitution cipher
  Substitution cipher
  In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...
  
  
• Tabula recta
  Tabula recta
  In cryptography, the tabula recta is a square table of alphabets, each row of which is made by shifting the previous one to the left...
  
  
• Transposition cipher
  Transposition cipher
  In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed...
  
  
• Vigenère cipher
  Vigenère cipher
  The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution....