328 - The Finite State Text Processing Machine

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Abdul Rauf
New poster
Posts: 1
Joined: Thu Nov 04, 2004 7:19 pm
Location: Pakistan
Contact:

Please help me in problem no 328 till today 2 P.M

Post by Abdul Rauf »

please sir help me as any one solve it perfactly please..........
other wise i will lose marks.
GODBLESS ON ME AND YOU
ALLAH HAFIZ
please provide other happy then you will recive happy

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar »

Abdul,

There goes an old adage:
Give a hungry man a fish - you feed him for a day.
Teach him how to fish - and you'll have fed him all his life.

This board, unfortunately subscribes to the latter view (except under rare circumstances, off course).We will help you no doubt but tell us what your
problem is exactly.When you ask us to solve it -- it becomes our problem and when we choose to solve it (if at all, that is, we choose to solve it)
depends wholly on us. :wink:

Go ahead try - and come back for hints, and not the solution.

The fun is in the journey, not the destination.

Regards,
Suman.

PS: We can get over our colonial hangovers, can't we?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

328 - The Finite State Text Processing Machine

Post by mamun »

I'm getting WA. Can somebody post some I/O plz?
In the input can the output of each transition be more than 1 character?
What should be the output of

Code: Select all

3
START 12
   \c START \c    !     FINIS \0
   A  TWO   a     E     TWO   e
   I  TWO   i     O     TWO   o
   U  TWO   u     a     TWO   A
   e  TWO   E     i     TWO   I
   o  TWO   O     u     TWO   U
TWO   4
  \c  TWO   \c    AEIOU START \c
   aeiou  START \c  !  FINIS  \0
FINIS 2
   \c  FINIS \0   \n    END   \n
This is some data for FSM number 3.
!    IGNORED
2
START 3
      \c    START \c
      Xx    SKIP  \c
      \n    END   \n
SKIP  5
      \\\b START \0
      aeiou START \b
      Xx    SKIP  \c
      \n    END   \n
      \c SKIP \\
Xax e
9
START 12
	az	A	A
	by	B	B
	cx	C	C
	dw	D	D
	ev	E	E
	fu	F	F
	gt	G	G
	hs	H	H
	\c	START	\c
	\b	START	\n
	\\	START	\0
	\n	START	\b
A 3
	abc 	B	B
	e	E	E
	\c	START	\c
B 4
	gh	C	C
	yz	D	D
	def	A	A
	\c	START	\c
C 3
	kl	G	G
	ij	B	B
	\c	START	\c
D 4
	v	B	B
	wx	D	D
	\n	END	\n
	\c	START	\c
E 3
	s	F	F
	u	A	A
	\c	START	\c
F 3
	r	H	H
	t	E	E
	\c	START	\c
G 3
	mn	C	C
	o	H	H
	\c	START	\c
H 4
	p	G	G
	s	F	F
	\c	START	H
	\n	END	\n
The input set and the output string are given as sequences of printable
characters with no embedded whitespace. Several special constructions may app-
ear in these, however. When \b appears it is to be interpreted as a blank.
Treat \n as an end of line, and \\ as a single backslash. The construction \0
(that is, backslash followed by zero) will appear only as an output string,
and means to print nothing when the transition occurs. The construction \c
appearing as an input set matches anything. That is, if none of the other trans-
itions are enabled and a transition has \c specified as its input set, then it
isenabled. When \c appears in an output string, it means to print the current
input character. This could appear several times in the same output string.
Lets' get over with it ...
a\ czwx
0
There is no trailing space in my input.
Looks like this is the first post about this topic. 8)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

My accepted program produces this output:

Code: Select all

Finite State Machine 1:
ThIs is sOme dAta fOr FSM numbEr 3.

Finite State Machine 2:
X xe
Finite State Machine 3:
THH
inpFE HHG AnD GhE oFEpFE HHrinG ArE GiEen
As
HHqFenCeHHoF prinGaBlE
ChArABtErHHDiGh
no
EmBAdDeD DhiGeHGaCe.
SEvErAl
HGeCBal
ConHHrFcGionHHmAy
App- Ear
in
GhEFe,
HHDeEer.
WHHn
B AppEarHHiG iHHGHHBA inGerprEtEd
As
A BlAnk. TrEaG n
As
An
EnD oF linE,
AnD 
As
A HHnGlE BaCGslAsHH
THH
ConHHrFcGion
0 (GhAt
iHH
BaCGslAsHHFolloDeD BD AEro)
Dill
AppEar
onlB As
An
oFEpFE HHrinG, AnD mEanHHGHHprinG noGhinG DhEn
GhE GrAnHHGion
oCcFHF.
THH
ConHHrFcGion
C
AppEarinG As
An
inpFE HHG mAtChEF AnBtHHnG.
THHG iHH
iF nonE oF GhE oGhEr
GrAnHH iGionHHArE EnABlEd
AnD A GrAnHHGion
HHHHC HGeCBAiEd
As
iGs
inpFE HHG,
GhEn
iG
iHHnABlEd.
WHHn
C AppEarHHin
An
oFEpFE HHrinG,
iG mEanHHGHHprinG GhE CurrEnG
inpFE ChArABtEr.
THHHHCoFlD AppEar
HHEerAl
GimEF in
GhE HHmE oFEpFE HHrinG. LEtHH
GeG oEer
DiGh
iG ... A\
CzDD
can the output of each transition be more than 1 character?
I think so. (At least, my program can handle such cases.)

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Thank you, mf. But I got the same output.
So where can be the trick? I think there is no whitespace in transition input, output, and state name. Am I right?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

I think there is no whitespace in transition input, output, and state name. Am I right?
Yes.
So where can be the trick?
The only thing I can think of, is that last line of FSM's description may end with garbage, as in:

Code: Select all

1
START 3
      AEIOUaeiou  START *
      \n          END   \n
      \c          START \c  this sentence isn't part of input.
This is input for example one.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

I'm little late. Had some problem in my computer. Wasn't able to work with the console.

Anyway, I think I'm handling the case like the one meant by mf properly. For example, for the input posted above I'm getting

Code: Select all

Finite State Machine 1:
Th*s *s *np*t f*r *x*mpl* *n*.
Am I correct?
Here are some cases where the transition output consists of multiple letters. Plz give the output of this

Code: Select all

2
START 4
      aeiou       START   <\bvowel\b>
      AEIOU       CAPITAL \b\\\c\\\b
      \n          END     \n\\ENDING_FROM_START\\\n
      \c          START   \c
CAPITAL 4
      aeiou       START   \b\\\c\\\b
      AEIOU       CAPITAL <\bVOWEL\b>
      \n          END     \n\\ENDING_FROM_CAPITAL\\\n
      \c          START   \c  this sentence isn't part of input.
This is a test where it'll end in "START". and here it ends.
2
START 4
      aeiou       START   <\bvowel\b>
      AEIOU       CAPITAL \b\\\c\\\b
      \n          END     \n\\ENDING_FROM_START\\\n
      \c          START   \c
CAPITAL 4
      aeiou       START   \b\\\c\\\b
      AEIOU       CAPITAL <\bVOWEL\b>
      \n          END     \n\\ENDING_FROM_CAPITAL\\\n
      \c          CAPITAL \c  this sentence isn't part of input.
this test will end in "CAPITAL". And here it's ending. BYE!
0

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Would anybody answer me plz?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Sorry, I just didn't notice your previous post.

Here's my output:

Code: Select all

Finite State Machine 1:
Th< vowel >s < vowel >s < vowel > t< vowel >st wh< vowel >r< vowel > < vowel >t'll < vowel >nd < vowel >n "ST \A\ RT". < vowel >nd h< vowel >r< vowel > < vowel >t < vowel >nds.
\ENDING_FROM_START\
Finite State Machine 2:
th< vowel >s t< vowel >st w< vowel >ll < vowel >nd < vowel >n "C \A\ P< VOWEL >T< VOWEL >L". < VOWEL >nd h \e\ r< vowel > < vowel >t's < vowel >nd< vowel >ng. BY \E\ !
\ENDING_FROM_CAPITAL\ 
(edit: output corrected)
Last edited by mf on Tue Jan 31, 2006 3:52 am, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Thank you mf.

Looks like you're ignoring punctuation marks. Why? \c doesn't include them? Moreover you're printing some \ where I'm not. For example look at BYE at the end of output. Maybe I misunderstood something?

This is what I get

Code: Select all

Finite State Machine 1:
Th< vowel >s < vowel >s < vowel > t< vowel >st wh< vowel >r< vowel > < vowel >t'll < vowel >nd < vowel >n "ST A RT". < vowel >nd h< vowel >r< vowel > < vowel >t < vowel >nds.
\ENDING_FROM_START\
Finite State Machine 2:
th< vowel >s t< vowel >st w< vowel >ll < vowel >nd < vowel >n "C A P< VOWEL >T< VOWEL >L". < VOWEL >nd h e r< vowel > < vowel >t's < vowel >nd< vowel >ng. BY E !
\ENDING_FROM_CAPITAL\

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Just a minute! Maybe I've found the matter with extra \. The trick is in transition outputs like

Code: Select all

\\c
\\\c
\\\\\c
But what about punctuation marks?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Finally I've got it accepted. The only error was the one that I had pointed out in my previous post. Here is the output of my solution for my given input

Code: Select all

Finite State Machine 1:
Th< vowel >s < vowel >s < vowel > t< vowel >st wh< vowel >r< vowel > < vowel >t'll < vowel >nd < vowel >n "ST \A\ RT". < vowel >nd h< vowel >r< vowel > < vowel >t < vowel >nds.
\ENDING_FROM_START\
Finite State Machine 2:
th< vowel >s t< vowel >st w< vowel >ll < vowel >nd < vowel >n "C \A\ P< VOWEL >T< VOWEL >L". < VOWEL >nd h \e\ r< vowel > < vowel >t's < vowel >nd< vowel >ng. BY \E\ !
\ENDING_FROM_CAPITAL\
So you see, the only difference from 2 accepted solutions is the apostroph. So we can safely assume that there is no such case in the input.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Oh, you're absolutely right! The output should contain apostrophs.

There was a bug in my 'tr'. I'm using an editor which writes files with \r\n line terminators, but I compile with cygwin, which treats \r as an extra character. So to pass proper input to my program I have to filter input file through tr -d '\r' command (which is supposed only to remove \r's). But it somehow also erased (??!) all apostrophes from input! I'm totally sorry!

repinel
New poster
Posts: 1
Joined: Sun Sep 03, 2006 4:13 am
Location: Brazil

Teste

Post by repinel »

pls, can somebody test this input and show the out?

Code: Select all

3
START 4
   \c START \c          X THREE -
   0  START \0A\0       1 TWO   \0B\0
TWO   4
   \c START \c          Y THREE -
   0  TWO   \0a\0       1 START \0b\0
THREE 4
   W  START +           Z TWO   +
   \c THREE \c          ! END   \\\b\0END\0\b\\\n
000110010101XyXYYW0101
0031011300X10101!03323
0
I've gotten:

Code: Select all

Finite State Machine 1:
AAABbAABabABXy-YY+ABab
AA3BabB3AA-10101\ END \
thnx.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

There might be something wrong with your input. Anyway I get the same output as yours.

Post Reply

Return to “Volume 3 (300-399)”