(1) Is an B2n N 0 Is a Regular Language? Is It an R.E?

(1) Is {an b2n | n ≥ 0} is a regular language? Is it an r.e?

How do you prove either way?

Is it a CF Grammar? CFL? How to prove either way?

Is {an b2n c3n | n ≥ 0} regular language? CFL? Recursive Language? Recursively Enumerable Language?

RE but not Recursive? Why do we care?

(2) Re & NFA: Write a Regular Expression for a language over Sigma={a,b}, where each string starts with two a’s AND finishes with two b’s.

Draw an NFA (NFA-e is ok) for the above language.

In & Out Examples?

(3) PDA for {an bn+m cm | n,m ≥ 1}, Extend for n,m=0.

Is it regular?

Do TM for above.

(4) Is the following string in L_u?

1110101010100110100101001011010001001000101100101000101011100

(1) Is {an b2n | n ≥ 0} is a regular language? Is it an r.e?

No! No!

How do you prove either way?

For RL draw DFA / NFA, or write a correct r.e.

Not RL: Prove by Pumping Lemma (PL):

Assume a DFA, size=n.

Choose a string s from L, with size …

Show why the PL applies.

What string the PL makes the DFA accept?

But, such a string is not in L è DFA is wrong è L is not RL.

Is it a CF Grammar? CFL? How to prove either way?

Grammar?

CFL, yes! Write a CFG / PDA.

Is {an b2n c3n | n ≥ 0} regular language? CFL? Recursive Language? Recursively Enumerable Language?

RE but not Recursive? Why do we care?

RL No! CFL No. RL yes. => Recursive yes => RE yes. => Not (RE but not Recursive)

RE means we can have a Halting TM for the language,

Proof of not CFL by CFL-Pumping Lemma (PL):

As above, but note the chosen string’s size,

And generated string’s (by PL) structure (uvxyz).

(2) Re & NFA: Write a Regular Expression for a language over Sigma={a,b}, where each string starts with two a’s AND finishes with two b’s.

aa(a+b)*bb

Draw an NFA (NFA-e is ok) for the above language.

In & Out Examples?

Follow the r.e to NFA-e translation theorem-proof.

(3) PDA for {an bn+m cm | n,m ≥ 1}, Extend for n,m=0.

Push for a’s and pop for b’s.

Reaching stack-bottom #, (possibly change state, and) start pushing for b’s and pop for c’s.

This time hitting # accept.

For n=0, m>0: start with b’s.

For n>0, m=0: stack-bottom # at end of string.

For n=0, m=0: q0 sees #: accept.

Is it regular?

Yes.

Do TM for above.

Cross a’s and b’s back and forth.

When a is finished scan right looking for b’s to cross against c’s now, use different tape symbol for b’s now.

Continue with crossing b’s against b’s back and forth.

When b’s are finished scan right in pre-final state looking for B.

If found, then accept.

For n=0, m>0: start with b’s

On finishing a’s, if scan right produces B rather than b, then the case is For n>0, m=0: accept.

For n=0, m=0: q0 sees B: accept.

(4) Is the following string in L_u?

1110101010100110100101001011010001001000101100101000101011100

Yes. ->q1 -0-> q1 -0-> q1 -B-> q2: accept, i.e. M accepts the following suffix.

Note: On hitting 1 after 0, the machine goes into infinite loop: 0-Right-1-Left-0-Right-1-…

e.g. on 0010 it will go into infinite loop.

However, the machine does accept 0(0)*:

->q1 -0- > q1(Right) –0-> q1(Right) -> …->q1-B-> q2(Left) -0-> q3: accept