What is the difference between formal and informal languages?

Language:

       Set of strings with rules. It is a subset of Kleene Star ∑* for some alphabet ∑.

It can be finite or infinite

Formal languages:

       The language that is concerned with some rules or syntax and words of that language gives some meanings

Informal languages:

       The language that is concerned with only some rules or syntax not with meaning. The words of that kind of language have no meaning.

English Language

          Learn          Lanre    

  •  Concerned with rules and meaning
  •  Informal language or Semantic language

Language1: Starts with L and end with e

 Learn          Lanre

  •  Concerned with just rules or syntax, not with meaning
  •  Formal language or syntactic language

An automaton focuses on formal languages

Alphabets:
  • Finite set of letters or symbols are called alphabets
  • ∑ = {a, b}, {0, 1}, {a, ab, baa}, {if, switch}
String
  • Combination of finite alphabets forms a string
  • S = ab, ba, bab, abb
Word
  • String that belongs to some language is called word
  • abbbb, bab, baaa  all belongs to language {a, b}
Null String
  • String having no alphabet is called null string
  • Represented by ε or λ
Length of string

Total number of alphabets in a string.

  • S = {a, b}   
    • |S| = abb  length of the string is 3                   
  • S = {a, ab}   
    • |S| = abab  length of the string is 2
  • S = λ     
    • |S| = λ   length of the string is 0
Reverse of a string
  • Represented by Rev(s) or sr
  • S = {a,b}   
    • |S|= |abb|R = baa
  • S = {a,ab}   
    • |S|= |aab|R = aba  ( “a” is s single letter and “ab” is another single letter, that’s why while reversing the string, “ab” will be written together as a whole and “a” will be written at the end for making it reversible)
Concatenation
  • S1 = ab                 S2 = bb
    • S1S2 = abbb
Union
  • S1 = aa                 S2 = ba
    • S1+S2 = aa + ba = ba + aa
  • S1 = λ                   S2 = aa
    • S1+S2 = λ  + aa = aa
Kleene star
  • The kleene star is a unary operator on a set of strings or symbols that gives the infinite set of all possible strings of all possible lengths over S including λ or ε.
  • It is represented by ∑*
  • ∑ = {a, b}
    • ∑* = { λ, a, b, ab, ba, aa, bb, ……………}
Kleene Closure / Plus
  • The kleene plus or closure is a unary operator on a set of strings or symbols that gives the infinite set of all possible strings of all possible lengths over S excluding ε or λ.
  • It is represented by ∑+
  • ∑ = {a, b}
    • += { a, b, ab, ba, aa, bb, ……………}

Related Posts

News Reporter