0
$\begingroup$

This is a school assignment, I am fairly new to DFA's.

L = {ww|w∈{0,1}*

I feel like I need to put this in words to understand how it works.

Translating L:

W can be a string of an infinite combination of 1s and 0s.
WW is just a string that repeats itself.

For example W="101011", WW = "101011101011".

Im not a 100% on this. Not really sure how to create a DFA out of this.

Am I correct with my "translation"? If you can help me further into making a DFA much appreciated.

$\endgroup$
  • $\begingroup$ Your language is not regular. $\endgroup$ – Yuval Filmus Feb 1 '18 at 6:35
1
$\begingroup$

You cannot make a DFA for this language because its not a Regular language in fact its not even a context free language so you can't even make a PDA for it

to prove its not regular and not context free you should use pumping lemma

but you can make a linear bounded automata for this language so therefore its a context sensitive language

hint for the linear bounded automata: put both of the w's in the tape and separate them with 0, then compare them.

also here's some examples for some of the strings in the language :

00 , 11 , 0101 , 1010 , 110110 ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.