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|R = |abb|R = baa
- S = {a,ab}
- |S|R = |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, ……………}
