[go: up one dir, main page]
Scribd
Upload
58 views5 pages

Toc Assignment

This document contains a program of a pushdown automaton (PDA) to recognize the language of strings of the form w#wR, where w is a string and wR is the reverse of w. It first provides the state diagram of the PDA with four states: W, ε, # and $. It then formally defines the PDA with its set of states Q, input alphabet Σ, stack alphabet Γ, transition function δ, initial state q0, and set of final states F. The document concludes by providing the C program that implements the PDA to check if a given input string is in the language w#wR.

Uploaded by

BaD BoY
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
58 views5 pages

Toc Assignment

This document contains a program of a pushdown automaton (PDA) to recognize the language of strings of the form w#wR, where w is a string and wR is the reverse of w. It first provides the state diagram of the PDA with four states: W, ε, # and $. It then formally defines the PDA with its set of states Q, input alphabet Σ, stack alphabet Γ, transition function δ, initial state q0, and set of final states F. The document concludes by providing the C program that implements the PDA to check if a given input string is in the language w#wR.

Uploaded by

BaD BoY
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

IUBAT – International University of Business Agriculture and

Technology

CSC 397

Theory of Computation

Assignment No: 02
Report on: Program of PDA to recognize w#𝑤 𝑅

Prepared For:

Dr. Ehteshamul Haque

Course Instructor

Prepared By:
Suvrho Mojumder
ID: 14303040
Section: D
Fall 2017

Submission Date
27/11/2017
State diagram for w#𝒘𝑹 :

W, εW W, 𝑤 𝑅  ε

ε ,ε  $ #, ε ε ε ,$  ε

Formal Definition of PDA forw#𝒘𝑹 :

The formal definition of PDA for the given pattern is given below:
P = {Q, ∑,Г, δ, q0, F}, where

Q = {ql, q2, q3, q4},

∑ = {a, b, c, d},

Г = {0, $}

F = {q4}
Program:
# include <stdio.h>

int main()

int i=0, tos=0, state=1;

char str[20], stak[20];

printf("\n input string W#W = ");

scanf("%s",str);

stak[tos]= '$'; tos++;

while(1)

if(state==1 && str[i] !='#'){state=1; stak[tos]=str[i]; tos++; i++; }

else

if(state==1 && str[i]=='#'){state=2; i++; tos--; }

else

if(state==2 && stak[tos]==str[i] ){state=2; tos--; i++; }

else

if(state==2 && stak[tos]=='$' && str[i]=='\0' ){state=3; break; }

else

break;

if(state==3)printf(" is valid ");

else

printf(" is not valid ");

return 0;
}

Output:

You might also like