Consider the problem of recognizing whether a particular string is in the language L = { s$s' : s is a possibly empty string of characters other than $ , s' = reverse( s )} Trace the execution of the language-recognition algorithm for each of the following strings, and show the contents of the stack at each step. a. a$a b. ab$ab c. ab$a d. ab$ba Pseudocode // Checks the string aString to verify that it is in language L. // Returns true if aString is in L, false otherwise. recognizeString(aString: string): boolean aStack = a new empty stack // Push the characters that are before the $ (that is, the characters in s) onto the stack i = 0 ch = character at position i in aString while (ch is not a '$') {     aStack.push(ch)    i++    ch = character at position i in aString } // Skip the $ i++ // Match the reverse of s inLanguage = true // Assume string is in language while (inLanguage and i < length of aString) {    if (!aStack.isEmpty()) {     stackTop = aStack.peek()    aStack.pop()    ch = character at position i in aString    if (stackTop equals ch)        i++ // Characters match else      inLanguage = false // Characters do not match (top of stack is not ch ) } else inLanguage = false // Stack is empty (first half of string is shorter // than second half) } if (inLanguage and aStack.isEmpty())      aString is in language else    aString is not in language

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
icon
Concept explainers
Question

Question:

Consider the problem of recognizing whether a particular string is in the language
L = { s$s' : s is a possibly empty string of characters other than $ , s' = reverse( s )}

Trace the execution of the language-recognition algorithm for each of the following strings, and show the contents of the stack at each step.

a. a$a
b. ab$ab
c. ab$a
d. ab$ba

Pseudocode

// Checks the string aString to verify that it is in language L.

// Returns true if aString is in L, false otherwise.

recognizeString(aString: string): boolean

aStack = a new empty stack

// Push the characters that are before the $ (that is, the characters in s) onto the stack

i = 0

ch = character at position in aString

while (ch is not a '$')

{

    aStack.push(ch)

   i++

   ch = character at position in aString

}

// Skip the $

i++

// Match the reverse of s

inLanguage = true // Assume string is in language

while (inLanguage and i < length of aString)

{

   if (!aStack.isEmpty())

{

    stackTop = aStack.peek()

   aStack.pop()

   ch = character at position in aString

   if (stackTop equals ch)

       i++ // Characters match

else

     inLanguage = false // Characters do not match (top of stack is not ch )

}

else

inLanguage = false // Stack is empty (first half of string is shorter

// than second half)

}

if (inLanguage and aStack.isEmpty())

     aString is in language

else

   aString is not in language

c++

Expert Solution
steps

Step by step

Solved in 3 steps with 16 images

Blurred answer
Knowledge Booster
Depth First Search
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education