... Seems like a trivial application of the pumping lemma. If L was regular, the pumping lemma would apply. Since there can only be one b in the string, there...
This can be proved by simple application of pumping lemma for regular languages If p is the pumping length, consider the string a^pba^3p which belongs to given...
Show proof that the following language over the alphabet {a,b} is not regular using pumping or cutting: L = {a ^i b^n |, n!=0, i=n or i=2n } Thanks, Pete...
Show proof that the following language over the alphabet {a,b} is not regular using pumping or cutting: L = {a ^i b^n |i, n!=0, i=n or i=2n } Thanks, Pete...
... What have you already done about this homework? Show your work and where you're stuck. Hint: consider the previous problem and the fact that regular ...
plzz solve these problems Q1. Consider the language S*, where S = {bb,a}. How many words does this language have of length 4? of length 5? of length 6? What...
plzz solve these problemss of theory of automata Q1. Consider the language S*, where S = {bb,a}. How many words does this language have of length 4? of length...
Hi all, I'm reviewing for my written qualifyings, please tell me if I have made a mistake. Okay to be a regular language it must be expressable by a DFA which ...
L1 = {a^n b^n c^k |n, k=0,1,2,....} The production rules would be as follows: S->WC W -> aWb | epsilon C -> cC | epsilon The trick here is to get the...
Hi, I am studying Theory of Computation and I would like to know about Decidability of Logical Theories. I could read some things in Sipser's book... Is there...
Hi! I'm suggesting a book Computability and Complexity Theory by Homer and Selman. It has a nice introduction about TM's and decidability. ... mais! ...
Hello to all; plz can any one help me in solving following question? plz also see the files section where i upload a question file Q1. Build an FA accepting...
Hello, This email message is a notification to let you know that a file has been uploaded to the Files area of the comp-sci-theory group. File :...
comp-sci-theory@yahoo...
Oct 14, 2003 3:35 pm
1255
hi, there would some one help me understand the padding argument used in analyzing complexity class. what kind of padding function f will be a proper one? ...
hi Please see my approach and if any corrections are welcome. For every one "a" push two "a" s on to the stack and for every "b" pop one "a" from the stack. ...
This is a tough problem that only experts would understand. Prove that the following language is not context-free. L1 = {a^3k b^2k c^k| k=0,1,2,.....} I'll be...
I can trace this set of configurations but I can't seem to explain what it does in English. For example, accepts all strings that have an even number of a's...
Hello, I need some help with creating the complete set of transition states for the following Turing machine: R[_] If anyone knows how to do this or where to...
hi, I am also working on 4.13. I will really appreciate any help with this problem. Thanks ... a ... language. ... reversed ... a ... 1* ... we ... is ... ...
hi, I need help on Sipser, chapter 4 and homework problem 4.13. I will appreciate any help on this homework as soon as possible, it is due tomorrow and I am a...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
