More examples

Ex. 4:
Describe as simply as possible in English the language corresponding to the regular expression a*b(a*ba*b)*a* .

Solution:
A string in the language can start and end with a or b, it has at least one b, and after the first b all the b's in the string appear in pairs. Any numbe of a's can appear any place in the string. Thus simply put, it is the set of strings over the alphabet { a, b } that contain an odd number of b's.
We will continue examples in next post..

Examples of Regular Grammars and Regular Expressions

Ex. 2:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that contain exactly two a's.

Solution:
A string in this language must have at least two a's. Since any string of b's can be placed in front of the first a, behind the second a and between the two a's, and since an arbitrasry string of b's can be represented by the regular expression b*, b*a b*a b* is a regular expression for this language.


Ex. 3:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that do not end with ab.

Solution:
Any string in a language over { a , b } must end in a or b. Hence if a string does not end with ab then it ends with a or if it ends with b the last b must be preceded by a symbol b. Since it can have any string in front of the last a or bb, ( a + b )*( a + bb ) is a regular expression for the language

Context-Free-Language (CFL)

A language L is said to be a Context-Free-Language (CFL) if its grammar is Context-Free. More precisely, it is a language whose words, sentences and phrases are made of symbols and words from a Context-Free-Grammar. Usually, CFL is of the form L=L(G). Given below are examples for CFG but not for CFL.
Here I am giving you one example of context-free grammar
Example:
A context-free grammar for the language consisting of all strings over {a,b} which contain a different number of a's to b's is
S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε
Here, T can generate all strings with the same number of a's as b's, U generates all strings with more a's than b's and V generates all strings with fewer a's than b's.

Deterministic Finite Automata (DFA)

DFAs are equivalent in computing power to NFAs (nondeterministic finite automata).On the other hand, DFAs are of strictly limited power in the languages they can recognize — many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA.
The classical example of a simply described language that no DFA can recognize is the language consisting of strings of the form anbn — some finite number of a's, followed by an equal number of b's. It can be shown that no DFA can have enough states to recognize such a language.
See you later with our next post….

Automata Step by Step

Now we will define “Sequence”

Sequence:
A sequence is an ordered list of objects (or events). Like a set, it contains members (also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and the exact same elements can appear multiple times at different positions in the sequence.

Now we will define “Language”.

Language(or Formal Language):

A Language is a set of strings over a given input alphabet.
As an example of formal language, an alphabet might be {a, b}and a string over that alphabet might be “ababba”

Automata Step by Step

Let’s see the definitions of “String”, “Alphabet”,” Sequence” and “Language”. Remember all above terms are connected. You can’t understand any of them without knowing the definitions of all of them.

String:

In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. These symbols are chosen from a predetermined set.

Example: Empty String (contains no symbols)

Length of Empty String is zero.

Now we will define “Alphabet”.

Alphabet:
An alphabet is a finite set of symbols.
Examples:
Binary Alphabet = {0, 1}
Unary alphabet= {1}
ASCII Alphabet= {…..A, B, C………, a, b, c…………}
Decimal Alphabet= {0, 1, 2…….8, 9}