Formal Languages

Introduction

flowchart TB
  subgraph eid[Recursively Enumerable]
    subgraph sid[Context Sensitive]
      subgraph fid[Context Free]
        subgraph rid[Regular]
        end
      end
    end
  end

style eid fill:#8f8,stroke:#000
style sid fill:#afa,stroke:#000
style fid fill:#cfc,stroke:#000
style rid fill:#fff,stroke:#000

Loading

Regular Languages

Regular languages are generated by regular grammars. Regular grammars have the two general restrictions:

1. all production rules have at most one non-terminal symbol;
2. that symbol is either always at the end or always at the start of the rule's right-hand side.

A regular grammar is either right regular or left regular. Right regular grammars definitions allow the following types of productions rules:

1. A $\rightarrow$ a
2. A $\rightarrow$ aB

where A and B stands for a non-terminal symbols and a is a terminal symbol. The set of non-terminal symbols is denoted by $\text{N}$. The set of terminal symbols is denoted by $\Sigma$. The set of production rules is denoted by $\text{P}$ and the start symbol is denoted by $\text{S}$. Using this notation we may define a formal regular grammar $\left< \text{N}, \Sigma, \text{P}, \text{S} \right>$, where the production rules in $\text{P}$ should be of the form mentioned earlier.

Example

1. S $\rightarrow$ N B S | N
2. N $\rightarrow$ D N | D
3. B $\rightarrow$ + | - | * | /
4. D $\rightarrow$ 0 | 1 | 2 | $\dots$ | 9

flowchart LR
  S0((0))
  S1(((1)))
  S2((2))

  S0 -- D --> S1
  S1 -- B --> S2
  S2 -- D --> S1
  S1 -- D --> S1

  style S0 fill:#aaa,stroke:#000
  style S1 fill:#8f8,stroke:#000
  style S2 fill:#fff,stroke:#000

Loading

Implementation

struct dfa
{
    unsigned int n;
    unsigned int start;
    unsigned int final;
    struct node **transitions;
};

struct node
{
    char symbol;
    unsigned int state;
    struct node *next;
};

char match(char *string, struct dfa *t);

Context Free Languages

A context free grammar is production allows the following type of production rule:

1. A $\rightarrow$ w

where A stands for a non-terminal symbol and w is string of terminals and non-terminal symbols. The set of non-terminal symbols is denoted by $\text{N}$. The set of terminal symbols is denoted by $\Sigma$. The set of production rules is denoted by $\text{P}$ and the start symbol is denoted by $\text{S}$. Using this notation we may define a formal regular grammar $\left< \text{N}, \Sigma, \text{P}, \text{S} \right>$, where the production rules in $\text{P}$ should be of the form mentioned earlier.

Example

1. S $\rightarrow$ ( S B S ) | N
2. N $\rightarrow$ D N | D
3. B $\rightarrow$ + | - | * | /
4. D $\rightarrow$ 0 | 1 | 2 | $\dots$ | 9

flowchart LR
  S0((0))
  S1(((1)))
  S2((2))
  S3((3))
  S4((4))
  S5((5))
  S6((6))
  S7(((7)))

  S0 -- "D,$:$" --> S1
  S1 -- "D,$:$" --> S1
  S0 -- "(,$:a" --> S2
  S2 -- "(,a:aa" --> S2
  S2 -- "D,a:a" --> S3
  S3 -- "D,a:a" --> S3
  S3 -- "B,a:a" --> S4
  S4 -- "(,a:aa" --> S2
  S4 -- "D,a:a" --> S5
  S5 -- "D,a:a" --> S5
  S5 -- "),a:$" --> S6
  S6 -- "B,a:a" --> S4
  S6 -- "),a:$" --> S6
  S6 -- "$,$:$" --> S7

  style S0 fill:#aaa,stroke:#000
  style S7 fill:#8f8,stroke:#000
  style S1 fill:#8f8,stroke:#000
  style S2 fill:#fff,stroke:#000
  style S3 fill:#fff,stroke:#000
  style S4 fill:#fff,stroke:#000
  style S5 fill:#fff,stroke:#000
  style S6 fill:#fff,stroke:#000

Loading

Implementation

struct dpa
{
    unsigned int n;
    unsigned int start;
    struct node *final;
    struct node *stack;
    struct transition **transitions;
};

struct node
{
    char symbol;
    struct node *next;
};

struct transition
{
    char input_symbol;
    char stack_symbol;
    char* stack_newtop;
    unsigned int state;
    struct node *next;
};

char match(char *string, struct dpa *t);