ZuoTi.Pro
Question

Theory of Computation - Push Down Automata (PDA) and Context Free Grammars (CFG)

Problem 1. From a language description to a PDA Show state diagrams of PDAs for the following languages: a. The set of strings over the alphabet fa, b) with twice as many as as bs. Hint: in class, we showed a PDA when the number of as is the same as the number of bs, based on the idea of a counter. + Can we use a similar counter in this case? b. {xcw l s-(a, b. c); w, x are strings over the alphabet (a, b: wR İs a substring of Try to make your PDAs as simple and elegant as possible (do not convert from CFG to PDA). Name your states and provide a short description of what each state represents. Also number each transition

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

PDA a,

0 0
Add a comment
Know the answer?
Add Answer to:
Theory of Computation - Push Down Automata (PDA) and Context Free Grammars (CFG) Problem 1. From...
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. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • 1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three...

    1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three types (), and . For example, (OOis in BAL but [) is not. Give a nondeterministic pushdown automata that recognizes the set of strings in BAL as defined in problem 1 above. Acceptance should be by accept state. 2. Give a context free grammar for the language L where L-(a"b'am I n>-o and there exists k>-o such that m-2*ktn) 3. Give a nondeterministic pushdown...

  • Give a context free grammar for the language L where L = {a"bam I n>:O and...

    Give a context free grammar for the language L where L = {a"bam I n>:O and there exists k>-o such that m=2"k+n) 3. Give a nondeterministic pushdown automata that recognizes the set of strings in L from question 3 above. Acceptance should be by accept state. 4. 5 Give a context-free grammar for the set (abc il j or j -k) ie, the set of strings of a's followed by b's followed by c's, such that there are either a...

  • Regular expressions, DFA, NFA, grammars, languages Regular Languages 4 4 1. Write English descriptions for the...

    Regular expressions, DFA, NFA, grammars, languages Regular Languages 4 4 1. Write English descriptions for the languages generated by the following regular expressions: (a) (01... 9|A|B|C|D|E|F)+(2X) (b) (ab)*(a|ble) 2. Write regular expressions for each of the following. (a) All strings of lowercase letters that begin and end in a. (b) All strings of digits that contain no leading zeros. (c) All strings of digits that represent even numbers. (d) Strings over the alphabet {a,b,c} with an even number of a's....

  • Part B - Automata Construction Draw a DFA which accepts the following language over the alphabet...

    Part B - Automata Construction Draw a DFA which accepts the following language over the alphabet of {0,1}: the set of all strings such that the number of 0s is divisible by 2 and the number of 1s is divisible by 5. Your DFA must handle all intput strings in {0,1}*. Here is a methodical way to do this: Figure out all the final states and label each with the shortest string it accepts, work backwards from these states to...

  • 3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa...

    3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa Give a leftmost derivation for the string. 3 points) (4 poiots) (5 points) (3 points) sECTION IWOLAttcmpt.any 3.(or 2) questions from this.scction Suppose we have two tokens: (1) the keyword if, and (2) id-entifiers, which are strings of letters other than if. Show the DFA for these tokens. Give a nightmost derivation for the string. Give a parse tree for the string i) Is...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT