Hi, I need help with the following 2 questions: 3.1 The language L={an bn-1 } wh
ID: 3879581 • Letter: H
Question
Hi, I need help with the following 2 questions:
3.1
The language L={an bn-1 } where n 1, is a language of all words with the following properties: • The words consist of strings of a’s followed by b’s. • The number of b’s is one less than the number of a’s.
Examples of words that belong to L are a, where n=1; aab, where n=2; aaabb, where n=3; aaaabbb, where n=4.
One way to test if a word w belong to this language L is to use a stack to check if the number of a’s balances the number of b’s.
Use the following header and write a function isInLanguageL2 that uses a stack to test if any word belongs to L. If w belongs to L then the isInLanguageL2 should return true otherwise isInLanguageL2 should return false. bool isInLanguageL2(string w);
Note the following: • Only words belonging to L should be accepted.
• The word bba does not belong to L.
3.2 The language L={an bn cn+1} where n 1, is a language of all words with the following properties: •
The words are made up of strings of a’s followed by b’ followed by c’s. • The number of a’s is always equal to the number of b’s.
• There is an extra c for every number of a’s and b’s.
• Examples of words that belong to L are abcc, where n=1; aabbccc, where n=2; aaabbbcccc, where n=3; aaaabbbbccccc, where n=4.
One way to test if a word w belong to this language is to use two stacks to check if the number of a’s balances the number of b’s and c’s. Use the provided header and write a function isInLanguageLc that uses stacks to test if any word belongs to L. bool isInLanguageLc(string w);
Hint: Push all a’s into the first stack and b’s into the second stack. Pop both stacks for every c’s that is in the string w. When both stacks are empty, there should be only one c left.
For 3.1:
I have this solution, but this ignores the order in which the words come:
// Example program witn main function for testing
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isInLanguageL2(string w) {
//Stack
stack<char> st;
//Counters
int aCounter = 0;
int bCounter = 0;
//Flags
bool aFound = false;
bool assertion = false;
//Iterate over word and extract each character
for(int i = 0; i< w.size(); i++) {
if(w[i] == 'a') {
//a found
st.push('A');
if(st.top() == 'B'){
st.pop();
}
aFound = true;
//console.log('b found!', aCounter);
} else {
if(w[i] == 'b') {
//b found = no need to set flag
st.push('B');
if(st.top() == 'A'){
st.pop();
}
}
}
}
// check difference
if(aFound) {
while(!st.empty()) {
if(st.top() == 'A') {
aCounter++;
} else if(st.top() == 'B') {
bCounter++;
}
st.pop();
}
if(aCounter - bCounter == 1) {
assertion = true;
}
} else {
return false;
}
return assertion;
}
int main()
{
string word;
cout <<"Please enter a word:";
getline (std::cin, word);
cout<< "Processing word..." << endl;
bool wordExists = isInLanguageL2(word);
cout<< (wordExists == true ? "Horray, word accepted!" : "Invalid word for language!") << endl;
}
Explanation / Answer
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isInLanguageL2(string w) {
//Stack
stack<char> st;
//Counters
int aCounter = 0;
int bCounter = 0;
//Flags
bool aFound = false;
bool assertion = false;
//Iterate over word and extract each character
for(int i = 0; i< w.size(); i++) {
if(w[i] == 'a') {
//a found
st.push('A');
if(st.top() == 'B'){
st.pop();
}
aFound = true;
//console.log('b found!', aCounter);
} else {
if(w[i] == 'b') {
//b found = no need to set flag
st.push('B');
if(st.top() == 'A'){
st.pop();
}
}
}
}
// check difference
if(aFound) {
while(!st.empty()) {
if(st.top() == 'A') {
aCounter++;
} else if(st.top() == 'B') {
bCounter++;
}
st.pop();
}
if(aCounter - bCounter == 1) {
assertion = true;
}
} else {
return false;
}
return assertion;
}
int main()
{
string word;
cout <<"Please enter a word:";
getline (std::cin, word);
cout<< "Processing word..." << endl;
bool wordExists = isInLanguageL2(word);
cout<< (wordExists == true ? "Horray, word accepted!" : "Invalid word for language!") << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.