nfa.h

Go to the documentation of this file.

 
#ifndef NFA_H_
#define NFA_H_
 
 /*  _   _ _____ _     */
 /* | \ | |  ___/ \    */
 /* |  \| | |_ / _ \   */
 /* | |\  |  _/ ___ \  */
 /* |_| \_|_|/_/   \_\ */
 
#include "graphs.h"
#include "graphs_transclos.h"
#include "type_abr.h"
#include "type_basic.h"
#include "type_binheap.h"
#include "type_boolarray.h"
#include "type_dequeue.h"
#include "words.h"
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
 
 

typedef struct {
    /* Mandatory */
    lgraph* trans; 
    dequeue* initials; 
    dequeue* finals; 
    letter* alphabet; 
 
    /* Optional */
    graph* trans_e; 
    lgraph* trans_i;    
    char** state_names; 
} nfa;
 

typedef struct {
    /* Mandatory */
    dgraph* trans; 
    uint initial; 
    uint nb_finals; 
    uint* finals; 
    letter* alphabet; 
 
    /* Optional */
    char** state_names; 
    bool** order; 
} dfa;
 
/*****************/
/*+ State names +*/
/*****************/

void nfa_print_state(const nfa*, 
    uint,        
    FILE*       
);

void dfa_print_state(const dfa*, 
    uint,        
    FILE*       
);

void nfa_reset_state_names(nfa* // The NFA.
);

void dfa_reset_state_names(dfa* A 
);

char** copy_all_names(char** names, 
    uint size 
);
 
/**********************/
/*+ Copy and release +*/
/**********************/

void nfa_delete(nfa* 
);

void dfa_delete(dfa* A 
);
 

nfa* nfa_copy(nfa* 
);

dfa* dfa_copy(dfa* A 
);

nfa* nfa_copy_exalpha(nfa*,    
    letter*, 
    uint      
);

dfa* dfa_copy_exalpha(dfa* A, 
    letter* alpha, 
    uint size 
);

void nfa_overwrite(nfa*, 
    nfa*  
);
 
/**************************************************************/
/*+ Computation of basic NFAs (used in Thompson's algorithm) +*/
/**************************************************************/

nfa* create_emptylang(void);

nfa* create_sing_epsilon(void);

nfa* create_sing_letter(letter 
);

nfa* create_sing_word(word* 
);
 
/*******************************/
/*+ Simple operations on NFAs +*/
/*******************************/
 

nfa* nfa_union(void* I1, 
    bool is_dfa_I1, 
    void* I2, 
    bool is_dfa_I2 
);

nfa* nfa_concat(void* I1, 
    bool is_dfa_I1, 
    void* I2, 
    bool is_dfa_I2 
);

nfa* nfa_star(nfa* 
);
 

nfa* dfa_star(dfa* 
);

nfa* nfa_plus(nfa* 
);

nfa* nfa_mirror(nfa* 
);

nfa* dfa_mirror(dfa* 
);

nfa* nfa_elimeps(nfa* 
);

void nfa_elimeps_mod(nfa* 
);

nfa* nfa_trim(nfa* 
);

dfa* dfa_trim(dfa* A 
);

void nfa_trim_mod(nfa* 
);
 
 
dfa* dfa_direct_product(dfa* A, 
    dfa* B 
);
 
/***********************************/
/*+ Generation of random automata +*/
/***********************************/

nfa* nfa_random(uint, 
    uint, 
    uint  
);

dfa* dfa_random(uint, 
    uint, 
    uint  
);
 
 
/*****************/
/*+ Information +*/
/*****************/

int nfa_nb_trans(nfa* 
);

bool nfa_is_det(nfa* 
);

bool nfa_is_comp(nfa* 
);

bool nfa_is_empty(nfa* 
);

bool nfa_accepts(nfa*, 
    word* 
);

dequeue* nfa_compute_runs(nfa*, 
    word* 
);
 

bool dfa_exists_path(dfa*, 
    uint,   
    uint,   
    bool* 
);

uint dfa_compute_run(dfa* A, 
    word* w 
);
 
 
 
 
 
 
 
 
/************************/
/* Partitions of states */
/************************/

nfa* nfa_merge_states(nfa*,  
    parti* 
);
 
 
 
/****************/
/*+ Conversion +*/
/****************/

dfa* detnfa_to_dfa(nfa* A
);

nfa* dfa_to_nfa(dfa* A 
);

nfa* dfa_to_nfa_exalpha(dfa* A, letter* alpha, uint size);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
#endif // NFA_H_