AIRCC's International Journal of Computer Science and Information Technology

K. M. Azharul Hasan ¹, Al-Mahmud ¹, Amit Mondal ¹, Amit Saha ¹

Affiliations
1 Department of Computer Science and Engineering (CSE), Khulna University of Engineering and Technology (KUET), Khulna-9203, BD

Abstract

We describe a Context Free Grammar (CFG) for Bangla language and hence we propose a Bangla parser based on the grammar. Our approach is very much general to apply in Bangla Sentences and the method is well accepted for parsing a language of a grammar. The proposed parser is a predictive parser and we construct the parse table for recognizing Bangla grammar. Using the parse table we recognize syntactical mistakes of Bangla sentences when there is no entry for a terminal in the parse table. If a natural language can be successfully parsed then grammar checking from this language becomes possible. The proposed scheme is based on Top down parsing method and we have avoided the left recursion of the CFG using the idea of left factoring.

Keywords

Context Free Grammar, Predictive Parser, Bangla Language processing, Parse Table, Top down and Bottom up Parser, Left Recursion.

Full Text

   

Al-Mahmud ¹

Affiliations
1 Department of Computer Science and Engineering (CSE), KUET, Khulna-9203, BD

Abstract

Solving University Class Scheduling Problem (UCSP) is a complex real-world combinatorial optimization task that has been extensively studied over the last several decades. Many meta-heuristic based techniques, including prominent swarm intelligence (SI) methods have been investigated to solve it in different ways. In this study, Ant Colony Optimization (ACO) based two methods are investigated to solve UCSP: ACO based method and ACO with Selective Probability (ACOSP). ACO is the well-known SI method that differs from other SI based methods in the way of interaction among individuals (i.e., ants); and an ant interacts with others indirectly through pheromone to solve a given problem. ACO based method considers probabilistically all the unassigned time slots to select next solution point for a particular course assignment. In contrast, ACOSP probabilistically selects next solution point for a particular course assignment from the selective probabilities. Such selective probability employment with ACO improves performance but reduces computational cost. The performances of the proposed methods have been evaluated comparing with Genetic Algorithm (GA) in solving real-world simple UCSPs. In addition, proposed methods are compared with each other for solving highly constrained UCSPs. Both the proposed methods outperformed GA and ACOSP was the best to solve the given problems.

Keywords

University Class Scheduling Problem (UCSP), Ant Colony Optimization (ACO), and Selective Probability (SP).

Full Text