Implementing DFA in C

Deterministic Finite Automata (DFA) is good model for recognizing Regular Expression (RegEx). The result of a RegEx is a language. So, Simply we conclude that “DFA decides that is a specific string in a specific language or not”. From now on, I won’t get in details of DFA and RegEx any more. If you’d like to learn these, I recommend you to watch this video. Remaing part of the blogpost is about implementing a DFA in C.

Assume we have a DFA like below.

An Example of a DFA

I’d like to implement a algorithm for this specific DFA. Without any reflection, anyone could choke numerous loops while designing. Besides, you will only have a algorithm for this specific DFA. It is not the smart method. I want to show you a generic and wisely method.

Firstly, Make a transaction table for this DFA. Columns represents alphabet and Rows represent states. Each elements in matrix show state number to go.

States\Alphabet01
S0S0S1
S1S2S0
S2S1S2

In this table, We have clear information about where to go at initial state. For example, Next alphabet symbol is 1 while DFA is in S1. So, DFA have to go S1.

Let’s assume W means input string.

#include <stdio.h>
#include <string.h> //Used for only strlen() function

int main(void){
    int i; //Counter

    int TransactionTable[3][2] = { //Row=state, Column=alphabet
    {0, 1},
    {2, 0},
    {1, 2}
    };

    int StartingState, AcceptingState, InitialState;

    StartingState = 0;
    AcceptingState = 0;
    InitialState = StartingState;

    char w[100] = "10001011101"; //String will be processed by DFA

    i = 0;
    while( i < strlen(w)){ // strlen(w) means size of string
        // w[i] is a char. for getting a value of a char, substracted by '0'
        InitialState = TransactionTable[InitialState][(w[i] - '0')];
        printf("InitialState: %d, SymbolToProcess: %d, #Transactions: %d\n", InitialState, w[i] - '0', i+1); //Only for information
        i++;
    }

    if( InitialState == AcceptingState ){
        printf("'%s' is Accepted!", w);
    }
    else{
        printf("'%s' is Rejected.", w);
    }

    return 0;
}


I passed the DFA as a Transaction Table Matrix. So, I have a generic solution for DFAs. That simple! If you’d like to make a implementation for different DFA, You have to just change TransactionTable matrix, StartingState and AcceptingState variables.

GNU and Keyboard Shortcuts in LXDE

I have recently attended GNU/Linux training at Istanbul Hackerspace. It was informal and eye-opening event for me. Besides, Philosophy of GNU is deeply impressed me. If you’d like to get more information about GNU like me, I recommend you to read Free Software, Free Society: Selected Essays of Richard M. Stallman book. I have been reading the book, too. It is avaible in Turkish too.

I have made a few decisions after the training like using free software as far as possible, removing Windows from my computers. So, Debian and LXDE have been my choices.

After installation, I have noticed that general keyboard shortcut of terminal (Ctrl+Alt+T) is not implemented in LXDE. After searching on a web, i have figuered how i will do.

In LXDE, general settings hold in ~/.config/openbox/lxde-rc.xml file. Keybindings, too.

Control keys (Ctrl, Fn, Windows Button, Alt) are implemented differently as shown in below.

Control KeyImplementation
ALTA-
CTRLC-
SHIFTS-
Windows ButtonW-

Lets impelement whole part.

<!-- Launch LXTerminal with Ctrl+Alt+T by FG -->
<keybind key="A-C-t">
  <action name="Execute">
    <command>lxterminal</command>
  </action>
</keybind>
  • LXDE useslxterminal. So, execute command of lxterminal is lxterminal too.
  • In Keybind part, requested keyboard shortcut is implemented.
  • Be careful about, implementing the add-on between <keyboard> and </keyboard>.

For nonworking volume buttons, this tutorial works too.

<!-- Volume Up by FG -->
<keybind key="A-F12">
  <action name="Execute">
    <command>amixer -D pulse sset Master 5%+</command>
  </action>
</keybind>
  • Volume button uses amixer program. For more information, execute man amixer at terminal.

Merhaba!

I’ve moved my old blog posts mostly about photography to tumblr. After that, I decided to use the domain for blogging about computer stuff i leared and tried. You are one of first visitors of the blog. Happy to see you, here.