Question

{w in (a|b|c)* | no of a's > no of b's} please write a TM. Give...

{w in (a|b|c)* | no of a's > no of b's} please write a TM. Give 2 strings one that satisfies and another string that rejects the turing machine

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

ANSWER:

NOTE: Please refer to the attached image for the answer.

NOTE:

1. qo is the initial state and qf is the final state.
2. R, L denotes movement to the right side and left side respectively in input tape.
3. denotes auxiliary symbol which denotes the processed symbol in the input string.
4. B denotes the blank symbol in the infinite input tape.

SAMPLE I/O:

String Result Explanation
1. aaabbaabbb Not accepted Number of a's and b's are equal in the given string
2. ababababbbaaa Accepted Number of a's is greater than number of b's in the given string
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Give me Turing Machine for the language {w in (a|b|c)* | no of a's > no...
Give me Turing Machine for the language {w in (a|b|c)* | no of a's > no of b's} ?
Write a Turing-machine style of algorithm to decide the language L2 given below. Use specific, precise,...
Write a Turing-machine style of algorithm to decide the language L2 given below. Use specific, precise, step-by-step English. So, describe how to test whether or not an input string is in the language L2 in finite time. No need to write a state diagram. L2 = {w : w has more a’s than it has b’s and c’s combined} over the alphabet Σ = {a, b, c}. Example strings: abaca ∈ L2. bcaa ∉ L2.
Write a Turing-machine style of algorithm to decide the language L1 given below. Use specific, precise,...
Write a Turing-machine style of algorithm to decide the language L1 given below. Use specific, precise, step-by-step English. So, describe how to test whether or not an input string is in the language L1 in finite time. No need to write a state diagram. L1 = {w : every ‘a’ within w is to the left of every ‘b’ within w} over the following alphabet Σ = {a, b, c}. In other words, you’re not allowed to have any ‘b’...
In C write a menu driven program to write your own string handling functions. Don’t use...
In C write a menu driven program to write your own string handling functions. Don’t use static arrays, ONLY dynamic memory allocation is allowed. 1. Convert a string to integer. 2. Concatenate two strings 3. Copy string to another string 4. Compare two strings 5. String length 6. Quit
Please write code in C++ and include headers files not std/bitsc: (Pattern matching) Write a program...
Please write code in C++ and include headers files not std/bitsc: (Pattern matching) Write a program that prompts the user to enter two strings and tests whether the second string is a substring in the first string. Suppose the neighboring characters in the string are distinct. Analyze the time complexity of your algorithm. Your algorithm needs to be at least O(n) time. Sample Run Enter a string s1: Welcome to C++ Enter a string s2: come matched at index 3
LB = {w|w e {a,b,c}^*, w =c^kbba^n, n<k}. 1. Is LB regular or not? 2. Give...
LB = {w|w e {a,b,c}^*, w =c^kbba^n, n<k}. 1. Is LB regular or not? 2. Give proof that supports your answer.
1. Please write the following in C++ also please show all output code and comment on...
1. Please write the following in C++ also please show all output code and comment on code. 2. Also, use CPPUnitLite to write all test and show outputs for each test. Write CppUnitLite tests to verify correct behavior for all the exercises. The modifications are aimed at making the exercises more conducive to unit tests. Write a function that swaps (exchanges the values of two integers). Use int* as the argument type. Write a second swap function using a reference...
(Longest common prefix, C-string, loop, char comparison) Write the prefix function to find the longest prefix...
(Longest common prefix, C-string, loop, char comparison) Write the prefix function to find the longest prefix of two strings using C-strings with the following header: void prefix( const char s1[ ], const char s2[ ], char commonPrefix[ ]) Write a test program that prompts the user to enter two C-strings and displays their common prefix. Sample run :- String 1: Programming is fun String 2: Program logic The common prefix is program. ---- Can you please explain the code too...
2) Regular Expressions NPTE: Please give specific answer. Thanks. Consider the following pairs of regular expression...
2) Regular Expressions NPTE: Please give specific answer. Thanks. Consider the following pairs of regular expression and strings. In which cases does the string match the corresponding regular expression? (a|b)+ baabaa [A-Z][a-z]+ [A-Z][a-z]+      George Washington (ab*a*b-)+ ab-ababab-aaaaaaaab- Q). Write a regular expression that will match any social security number (as in 123-45-6789).
Please write in C++. Write down the pseudo-code for Fibonacci sequence and give the Big-Oh bound...
Please write in C++. Write down the pseudo-code for Fibonacci sequence and give the Big-Oh bound for your algorithm.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT