Recognition of Parts of Speech (POS) Using C
Objective
The objective of this experiment is to identify and recognize different parts of speech
(PRONOUN, VERB, ARTICLE, NOUN, ADVERB) in a given set of words using a static
dictionary-based approach in C programming.
Theory
Parts of speech are categories of words based on their function in a sentence. The main parts of
speech include:
Noun – Name of a person, place, thing, or idea.
Pronoun – Replaces a noun in a sentence.
Verb – Indicates an action or state of being.
Article – Defines a noun as specific or unspecific (e.g., "a", "an", "the").
Adverb – Modifies a verb, adjective, or other adverbs, often indicating manner, time, or
place.
In this experiment, a static array-based approach is used to map words to their corresponding
parts of speech. This is a simple form of dictionary-based POS tagging, where each word is
pre-defined with its POS tag.
Tools / Software Used
Programming Language: C
Compiler: GCC / Dev-C++ / Code::Blocks / OnlineGDB
Program
#include <stdio.h>
#include <string.h>
int main() {
// Array of words
char *words[] = {"I", "eat", "an", "apple", "quickly"};
// Array of corresponding parts of speech
char *pos[] = {"PRONOUN", "VERB", "ARTICLE", "NOUN", "ADVERB"};
int n = 5;
// Loop through each word and print its part of speech
for(int i = 0; i < n; i++) {
printf("%s -> %s\n", words[i], pos[i]);
}
return 0;
}
Flowchart
START
|
v
Initialize array of words and their POS tags
|
v
For each word in the array
|
v
Print word and corresponding POS
|
v
END
Input
The program uses a static input array of words:
"I", "eat", "an", "apple", "quickly"
Output
I -> PRONOUN
eat -> VERB
an -> ARTICLE
apple -> NOUN
quickly -> ADVERB
Result
The program successfully identifies the part of speech for each word in the input array using a
static dictionary approach.
Discussion
This experiment demonstrates a simple method for recognizing parts of speech in C using a pre-
defined dictionary. While this approach works for small fixed datasets, real-world POS tagging
requires more advanced algorithms such as rule-based or statistical methods.
DFA Simulation to Accept Strings Ending with "01" Using C
Objective
To design and implement a Deterministic Finite Automaton (DFA) in C that accepts all strings
ending with the substring "01".
Theory
A Deterministic Finite Automaton (DFA) is a theoretical machine used in computer science to
recognize patterns or languages. It consists of:
1. States (Q): Finite set of states the DFA can be in.
2. Alphabet (Σ): Set of input symbols.
3. Transition Function (δ): Rules that describe state changes for each input symbol.
4. Start State (q0): The initial state.
5. Accept States (F): Set of states in which the string is accepted.
Problem Statement:
Design a DFA that accepts strings ending with "01".
States: q0 (start), q1, q2 (accepting)
Alphabet: 0, 1
Transitions:
o q0 → 0 → q0
o q0 → 1 → q1
o q1 → 0 → q2
o q1 → 1 → q1
o q2 → 0 → q2
o q2 → 1 → q1
Accept State: q2
Tools / Software Used
Programming Language: C
Compiler: GCC / Dev-C++ / Code::Blocks / OnlineGDB
Program / Code
#include <stdio.h>
#include <string.h>
// Function to simulate DFA
int dfa_accepts(char str[]) {
char state = 'q0'; // Start state
int len = strlen(str);
for(int i = 0; i < len; i++) {
char c = str[i];
if(state == 'q0') {
state = (c == '0') ? 'q0' : 'q1';
} else if(state == 'q1') {
state = (c == '0') ? 'q2' : 'q1';
} else if(state == 'q2') {
state = (c == '1') ? 'q0' : 'q2';
}
}
return state == 'q2'; // Accept if ending in q2
}
int main() {
char test_string[] = "1101"; // Input string
if(dfa_accepts(test_string))
printf("Accepted\n");
else
printf("Rejected\n");
return 0;
}
Flowchart
START
|
v
Initialize state = q0
|
v
For each character in string:
|
+--> If state == q0:
| 0 -> q0
| 1 -> q1
|
+--> If state == q1:
| 0 -> q2
| 1 -> q1
|
+--> If state == q2:
0 -> q2
1 -> q1
|
v
End of string? --> Yes
|
v
Is state = q2? --> Yes -> ACCEPTED
--> No -> REJECTED
|
v
END
Input
The DFA accepts binary strings, e.g.:
"1101"
"1001"
"01"
"1010" (This one will be rejected)
Output
For input string "1101":
Accepted
Explanation: The string ends with "01", so the DFA reaches the accepting state q2.
Result
The DFA correctly identifies whether a string ends with "01" by simulating the states according
to the defined transition rules.
Discussion:
This experiment demonstrates the implementation of a DFA using C programming. The DFA
accurately simulates state transitions and accepts strings that satisfy the condition of ending with
"01". This shows how theoretical concepts of automata can be implemented practically.
Title
NFA Simulation to Accept Strings Containing "ab" or "ba" Using C
Objective
To design and implement a Non-deterministic Finite Automaton (NFA) in C that accepts all
strings containing the substring "ab" or "ba".
Theory / Background
A Non-deterministic Finite Automaton (NFA) is similar to a DFA but allows multiple
transitions for the same input symbol from a given state, including transitions to multiple states
or none.
Key characteristics of an NFA:
1. States (Q): Finite set of states.
2. Alphabet (Σ): Set of input symbols.
3. Transition Function (δ): Can return multiple next states for a given state and input
symbol.
4. Start State (q0): Initial state.
5. Accept States (F): States in which the input string is accepted.
Problem Statement:
Design an NFA that accepts strings containing either "ab" or "ba".
States: q0 (start), q1, q2 (accept "ab"), q3, q4 (accept "ba")
Alphabet: a, b
Accept States: q2, q4
Transition Rules:
o From q0:
a → q0, q1
b → q0, q3
o From q1:
b → q2
o From q3:
a → q4
The NFA accepts a string if any path reaches an accepting state.
Tools / Software Used
Programming Language: C
Compiler: GCC / Dev-C++ / Code::Blocks / OnlineGDB
Program / Code
#include <stdio.h>
#include <string.h>
#define MAX_STATES 10
// Function to simulate NFA
int nfa_accepts(char str[]) {
char states[MAX_STATES]; // current states
int count = 1;
states[0] = '0'; // start state q0
int len = strlen(str);
for(int i = 0; i < len; i++) {
char c = str[i];
char next_states[MAX_STATES];
int next_count = 0;
for(int j = 0; j < count; j++) {
char state = states[j];
if(state == '0') { // q0
if(c == 'a') { next_states[next_count++] = '0';
next_states[next_count++] = '1'; }
if(c == 'b') { next_states[next_count++] = '0';
next_states[next_count++] = '3'; }
} else if(state == '1') { // q1
if(c == 'b') next_states[next_count++] = '2'; // q2
} else if(state == '3') { // q3
if(c == 'a') next_states[next_count++] = '4'; // q4
}
}
count = next_count;
memcpy(states, next_states, count);
}
// Check if any state is accepting
for(int i = 0; i < count; i++) {
if(states[i] == '2' || states[i] == '4') return 1; // accepted
}
return 0; // rejected
}
int main() {
char test_string[] = "aba";
if(nfa_accepts(test_string))
printf("Accepted\n");
else
printf("Rejected\n");
return 0;
}
Flowchart
START
|
v
Initialize current states = {q0}
|
v
For each character in the input string:
|
+--> For each current state:
| Apply NFA transition rules
| Add resulting states to next states
|
v
Update current states = next states
|
v
End of string?
|
v
Check if any current state is accepting (q2 or q4)
|
/ \
Yes No
/ \
ACCEPTED REJECTED
|
v
END
Input
The NFA accepts strings over the alphabet {a, b}, e.g.:
"aba" → Accepted
"baba" → Accepted
"aabb" → Accepted
"aaaa" → Rejected
"bbb" → Rejected
Output
For input string "aba":
Accepted
Explanation: The string contains "ab", so one path reaches the accepting state q2.
Result
The NFA correctly identifies strings containing "ab" or "ba" using multiple possible transitions
from each state. Strings not containing these substrings are rejected.
Discussion
This experiment demonstrates the non-deterministic nature of NFAs, where multiple paths are
explored simultaneously. The NFA simulation in C successfully identifies strings containing
"ab" or "ba" and highlights the difference between deterministic and non-deterministic
automata.
Using Start State in LEX to Handle Multi-line C-style Comments
Objective
To use LEX start states to ignore multi-line C-style comments (/* ... */) while processing
the rest of the input text.
Theory
LEX allows start states, which let the scanner behave differently depending on the context. In
this experiment:
INITIAL state: normal scanning
COMMENT state: ignore all characters until "*/" is encountered
This approach ensures that multi-line comments do not interfere with code processing.
Tools / Software Used
LEX/Flex – Lexical analyzer
C Compiler (GCC)
IDE/Text Editor – Code::Blocks, Dev-C++, or terminal
Program / Code
%{
#include <stdio.h>
/* This program demonstrates the use of start states in LEX
to handle multi-line C-style comments */
%}
/* Define an exclusive start state named COMMENT */
%x COMMENT
%%
/* When "/*" is detected, switch to COMMENT state */
"/*" { BEGIN(COMMENT); }
/* In COMMENT state, when "*/" is detected, return to INITIAL state */
<COMMENT>"*/" { BEGIN(INITIAL); }
/* In COMMENT state, ignore all other characters including newline */
<COMMENT>.|\n { /* skip comment content */ }
/* In INITIAL state, print all characters as usual */
.|\n { ECHO; }
%%
int main() {
printf("Enter input (with comments) to test comment removal:\n");
yylex();
return 0;
}
Input
/* This is a comment */
int main() {
printf("Hello World");
}
Output
int main() {
printf("Hello World");
}
Result
The program successfully ignored multi-line C-style comments while displaying the remaining
code.
Discussion
LEX start states can effectively handle context-sensitive scanning, such as multi-line comments,
without affecting normal input processing.
1. back to INITIAL state after ending a comment.
Counting Characters, Words, and Lines Using LEX
Objective
To write a LEX program that counts the number of characters, words, and lines in a given text
input.
Theory / Background
LEX can scan input character by character and apply rules to increment counters:
\n → new line
[ \t]+ → spaces/tabs
[A-Za-z0-9]+ → words
. → any other character
The yyleng variable contains the length of the matched text.
Tools / Software Used
LEX/Flex
C Compiler (GCC)
IDE/Text Editor
Program / Code
%{
int chars = 0; /* Total characters */
int words = 0; /* Total words */
int lines = 0; /* Total lines */
/* Program counts characters, words, and lines in input */
%}
%%
/* Newline: increment line count and character count */
\n {
lines++;
chars++;
}
/* Spaces and tabs: increment character count */
[ \t]+ {
chars += yyleng;
}
/* Words: increment word and character count */
[A-Za-z0-9]+ {
words++;
chars += yyleng;
}
/* Any other single character: increment character count */
. {
chars++;
}
%%
int main() {
printf("Enter text to count characters, words, and lines:\n");
yylex(); /* Start scanning input */
/* Display results */
printf("\nAnalysis Complete:\n");
printf("Characters: %d\n", chars);
printf("Words: %d\n", words);
printf("Lines: %d\n", lines);
return 0;
}
Input
Hello World
This is LEX
Output
Characters: 21
Words: 5
Lines: 2
Result
The program correctly counted the characters, words, and lines from the input.
Discussion
LEX can efficiently scan text and apply counters for characters, words, and lines using simple
pattern rules.
3 – Recognizing Words Using LEX
Title
Recognizing and Printing Words from Input Using LEX
Objective
To write a LEX program that recognizes and prints all words from input text.
Theory / Background
LEX can identify patterns like [a-zA-Z]+ to detect words. Using rules, we can print each word
while ignoring punctuation, numbers, and other characters.
Tools / Software Used
LEX/Flex
C Compiler (GCC)
IDE/Text Editor
Program / Code
%{
#include <stdio.h>
/* Program to recognize words in input */
%}
%%
/* Match sequences of letters as words and print them */
[a-zA-Z]+ {
printf("Word: %s\n", yytext);
}
/* Ignore all other characters (numbers, punctuation, spaces) */
. {
/* Do nothing */
}
%%
int main() {
printf("Enter text to extract words:\n");
yylex(); /* Start lexical analysis */
printf("Word recognition complete.\n");
return 0;
}
Input
Hello, world! Welcome to LEX.
Output
Word: Hello
Word: world
Word: Welcome
Word: to
Word: LEX
Result
The program successfully recognized and printed all words in the input text, ignoring
punctuation and numbers.
Discussion
LEX allows easy identification and extraction of words using regular expressions. Words can be
processed individually for further analysis or processing.