Program that accepts inputs of the form 1^n 2^{n^2} 0

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Form Program
Click For Summary
SUMMARY

The forum discussion centers on creating a RAM program that accepts inputs of the form 1^n 2^{n^2} 0. The participants refine their code to ensure it correctly counts the number of 1's and 2's, validating the input format. Key instructions include using JZERO and JGTZ for control flow, and ensuring that the program only accepts the specified symbols. The final version of the RAM program effectively checks the input and outputs 1 for valid sequences and 0 for invalid ones.

PREREQUISITES
  • Understanding of RAM (Random Access Machine) programming concepts
  • Familiarity with control flow instructions such as JZERO and JGTZ
  • Knowledge of input validation techniques in programming
  • Basic arithmetic operations and their implementation in assembly-like languages
NEXT STEPS
  • Study RAM programming techniques for input validation
  • Learn about control flow mechanisms in assembly languages
  • Explore advanced input parsing strategies for formal languages
  • Investigate error handling in RAM programs and similar architectures
USEFUL FOR

Students and developers interested in theoretical computer science, particularly those working with RAM programming and input validation techniques. This discussion is also beneficial for anyone looking to understand the implementation of formal language acceptance criteria in programming.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to write a RAM program to accept all inputs of the form $1^n 2^{n^2} 0$.

The instructions of the RAM machine are the following:

LOAD a ; c(0) ← v(a), c(i) is the integer stored in register i (the contents of register i), v(a) is the value of operand a
(v(=i)=i, v(i)=c(i), v(*i)=c(c(i)) )

STORE i ; c(i) ← c(0)
STORE *i ; c(c(i)) ←c(0)

ADD a ; c(0) ← c(0)+v(a)

SUB a ; c(0) ← c(0)-v(a)

MULT a ; c(0) ← c(0) × v(a)

DIV a ; c(0) ← ⌊c(0)/v(a)⌋

READ i ; c(i) ← current input symbol
READ *i ; c(c(i)) ← current input symbol. The input tape head moves one square right in either case.

WRITE a ; v(a) is printed on the square of the output tape currently under the output tape head. Then the tape head is moved one square right.

JUMP b ; The location counter is set to the instruction labeled b.

JGTZ b ; The location counter is set to the instruction labeled b if c(0)>0; otherwise, the location counter is set to the next instruction.

JZERO b ; The location counter is set to the instruction labeled b if c(0)=0; otherwise, the location counter is set to the next instruction.

HALT ; Execution ceases.


I have done the following:

Code: 
Read x from input
d=0, s=0
while x!=0
       if x-1=0
           d=d+1
       else
           s=s+1
       Read x from input
p=d*d
r=s-p
if r=0
   Write 1

Then the RAM program is the following:

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while: LOAD 1
       JZERO endwhile 

LOAD 1
SUB =1
JGTZ two

LOAD 2
ADD =1
STORE 2

two: LOAD 3
     ADD =1
     STORE 3

READ 1

endwhile:  LOAD 2
           MULT 2
           STORE 4

           LOAD 3
           SUB 4
           STORE 5

LOAD 5
JZERO output
HALT
output: WRITE =1
        HALT

Is this correct?? (Wondering)
 
Technology news on Phys.org
Hi! (Smile)

mathmari said:
I have to write a RAM program to accept all inputs of the form $1^n 2^{n^2} 0$.
Code: 
Read x from input
d=0, s=0
while x!=0
       if x-1=0
           d=d+1
       else
           s=s+1
       Read x from input
p=d*d
r=s-p
if r=0
   Write 1

Suppose we give the input 1212220.
Will it be accepted? (Wondering)

And what happens to 1134560? (Wondering)
 
I like Serena said:
Suppose we give the input 1212220.
Will it be accepted? (Wondering)

It will be accepted... (Doh)

So, we have to make sure that an input will be accepted if all $1$'s are all together at the beginning of the string and then the $2$'s follow, right?? (Wondering)

I like Serena said:
And what happens to 1134560? (Wondering)

And the program has to accept only the symbols $1$ and $2$, right?? (Wondering)

I tried it again... (Nerd)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
else
    Write 0

Is it better now?? (Wondering)
 
mathmari said:
So, we have to make sure that an input will be accepted if all $1$'s are all together at the beginning of the string and then the $2$'s follow, right?? (Wondering)

And the program has to accept only the symbols $1$ and $2$, right?? (Wondering)

Right! (Nod)
I tried it again... (Nerd)
Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
else
    Write 0
Is it better now?? (Wondering)

Much better! (Nod)

Still, if the input is not accepted, we now sometimes get 0 and sometimes we get nothing at all. (Worried)
 
I like Serena said:
Still, if the input is not accepted, we now sometimes get 0 and sometimes we get nothing at all. (Worried)

Why do we get sometimes nothing at all?? (Wondering)
 
mathmari said:
Why do we get sometimes nothing at all?? (Wondering)

What happens with 11220? (Wondering)
 
I like Serena said:
What happens with 11220? (Wondering)

Is it maybe as followed?? (Wondering)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
    else
       Write 0
else
    Write 0
 
mathmari said:
Is it maybe as followed?? (Wondering)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
    else
       Write 0
else
    Write 0

That will do the trick!
Good! (Sun)
 
I like Serena said:
That will do the trick!
Good! (Sun)

Great! (Happy)

So, is the RAM program the following?? (Wondering)

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while1: LOAD 1
       SUB =1
       JGTZ endwhile1 

LOAD 2
ADD =1
STORE 2

READ 1

JUMP while1

endwhile1: while2: LOAD 1
                   SUB =2
                   JGTZ endwhile2

LOAD 3
ADD =1
STORE 3

READ 1

JUMP while2

endwhile2:  LOAD 1
            JGTZ N
           
LOAD 2          
MULT 2
STORE 4

LOAD 3
SUB 4
STORE 5

LOAD 5
JZERO output
WRITE =0
HALT
output: WRITE =1
        HALT

N: WRITE =0
   HALT
 
  • #10
mathmari said:
Great! (Happy)

So, is the RAM program the following?? (Wondering)

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while1: LOAD 1
       SUB =1
       JGTZ endwhile1 

LOAD 2
ADD =1
STORE 2

READ 1

JUMP while1

endwhile1: while2: LOAD 1
                   SUB =2
                   JGTZ endwhile2

LOAD 3
ADD =1
STORE 3

READ 1

JUMP while2

endwhile2:  LOAD 1
            JGTZ N
           
LOAD 2          
MULT 2
STORE 4

LOAD 3
SUB 4
STORE 5

LOAD 5
JZERO output
WRITE =0
HALT
output: WRITE =1
        HALT

N: WRITE =0
   HALT

You have a couple JGTZ's in there that I think should be JZERO's. (Worried)

And I think WRITE =0 is not an allowed instruction. (Wasntme)
 
  • #11
I like Serena said:
You have a couple JGTZ's in there that I think should be JZERO's. (Worried)

Why should they be JZERO?? (Wondering)

The loop is executed while [m]x-1=0[/m].
So, it goes to endwhile when [m]x-1>0[/m], or not??
I like Serena said:
And I think WRITE =0 is not an allowed instruction. (Wasntme)

Why isn't it an allowed instruction?? (Wondering)

So, should I just write [m]HALT[/m]??
 
  • #12
mathmari said:
Why should they be JZERO?? (Wondering)

The loop is executed while [m]x-1=0[/m].
So, it goes to endwhile when [m]x-1>0[/m], or not??

It is supposed to go to endwhile when [m]x-1≠0[/m].
That is different, is it not? :confused:More to the point, suppose your input is $1121110$.
What will happen in your RAM code? (Wondering)
Why isn't it an allowed instruction?? (Wondering)

Mmh... I guess it is allowed.
I had the impression that WRITE needed to have the number of a register as parameter.
But rereading the spec, I guess it can also be an actual number. (Blush)
 
  • #13
I like Serena said:
It is supposed to go to endwhile when [m]x-1≠0[/m].
That is different, is it not? :confused:

JZERO endwhile means that the location counter is set to the instruction labeled endwhile if c(0)=0; otherwise, the location counter is set to the next instruction.

And JGTZ endwhile means that the location counter is set to the instruction labeled endwhile if c(0)>0; otherwise, the location counter is set to the next instruction.

So, which of them do we have to use?? (Wondering)

I like Serena said:
More to the point, suppose your input is $1121110$.
What will happen in your RAM code? (Wondering)

Do we have to use an if statement after the second while ??

Code: 
if x-1=0
   Write 0

(Wondering)
 
  • #14
mathmari said:
JZERO endwhile means that the location counter is set to the instruction labeled endwhile if c(0)=0; otherwise, the location counter is set to the next instruction.

And JGTZ endwhile means that the location counter is set to the instruction labeled endwhile if c(0)>0; otherwise, the location counter is set to the next instruction.

So, which of them do we have to use?? (Wondering)

You are testing for "greater than", when the test should be for "inequality".
I suggest using JZERO to implement a test for inequality.
Do we have to use an if statement after the second while ??

Code: 
if x-1=0
   Write 0

(Wondering)

Let's see... (Thinking)

You have:
Code: 
while x-1=0
  do statements

How about encoding it with:
Code: 
while:
  SUB =1
  JZERO do
  JUMP endwhile
do:
  statements
  JUMP while
endwhile:
(Wondering)
 
  • #15
I like Serena said:
You are testing for "greater than", when the test should be for "inequality".
I suggest using JZERO to implement a test for inequality.
We have

Code: 
while x-1=0
    d=d+1
    Read x from input

So, isn't the while loop executed while [m]x-1=0[/m] ?? (Wondering)

When we write

Code: 
JZERO endwhile

doesn't this mean that the while loop ends when [m]x-1=0[/m] ?? (Wondering)

Or haven't I understood it right?? (Wondering)
 
  • #16
mathmari said:
We have

Code: 
while x-1=0
    d=d+1
    Read x from input

So, isn't the while loop executed while [m]x-1=0[/m] ?? (Wondering)

Yes... (Thinking)

When we write

Code: 
JZERO endwhile

doesn't this mean that the while loop ends when [m]x-1=0[/m] ?? (Wondering)

Or haven't I understood it right?? (Wondering)

Also true.
That's why we should use [m]JZERO do[/m] instead, meaning we jump to the do-part of the while loop instead of the end of the while loop. (Wasntme)
 

Similar threads

MHB Converting Recursion into Loops for Computing n^n
  • · Replies 15 ·
Replies
15
Views
3K
MHB Read numbers and print them in sorted order
  • · Replies 8 ·
Replies
8
Views
2K
Python Partial pivoting in getting the reduced row echelon form of a matrix
  • · Replies 2 ·
Replies
2
Views
2K
Character pattern program -- Print large words using "X" characters
  • · Replies 12 ·
Replies
12
Views
3K
Is this computability theory proof correct?
  • · Replies 1 ·
Replies
1
Views
2K
Adding 2 and 3 digit capacity for assembly program
  • · Replies 4 ·
Replies
4
Views
5K
Python Simple code example of transforming matrix into upper triangular form
  • · Replies 3 ·
Replies
3
Views
2K
C/C++ Matrix33 in C++: Create, Add, Check & Program
  • · Replies 25 ·
Replies
25
Views
3K
Python Python: Semidefinite program with CVXPy 'Error parsing inputs'
  • · Replies 2 ·
Replies
2
Views
2K
Fortran Errors in Fortran code for solving Laplace's equation in 3D
  • · Replies 4 ·
Replies
4
Views
3K