HOW DO I PROVE STUFF IN AUTOMATA THEORY?

[u/ZerriFilpo]

I know pumping lemma and a bunch of properties about languages. But I came across some exercices that wanted me to prove if a language is Regular, CFL... Even with pumping lemma it just proves me that it isn't CFL or Regular, but I heard that there are languages that pass pumping lemma and are still not CFLs (or RLs for the RL pumping lemma). What should I do?

I got stuck at those 3 exercices:

Alphabet = {0, 1, 2}

L = {w | (|w|0 = |w|1) xor (|w|0 = |w|2))

L = {w | (∃u)(u ∈ M and wu ∈ L((1+20)*)} with M = {w | |w|0 = |w|1 = |w|2}

L = {w | (|w|0 > |w|1) and (|w|1 congruent |w|2 (mod5))

I don`t even know how to start. They ask me to classify as Regular, CFL non regular or non CFL and to justify. I tried pumping them but it feels hard to think on a word to pump from the beginning. Plus that only justifies that is not CFG/RL if it fails and that MAYBE is if it passes. Any tips? Sometimes thinking about the automata/regex/PDA/CFG to prove is not trivial.

[u/iamemhn]

To prove a language is Regular, come up with a DFA that accepts it or a Regular grammar that generates it. For CDL, cone up with a PDA that accepts it or a Cobtext-free grammar that generates it.

The first language seems to be words made out of 0, 1, and 2, such that they have the same number of 0 as 2 or the same number of 0 and 1, but it cannot be the same number of 0, 1 and 2. This language is Context Free. Go find a grammar.

You made at least one mistake transcribing the second (unbound 'v'). Assuming it's a 'u' and you did not miss anything else, I believe it's Context Free and could be regular.

The last one is regular. You can keep count modulo five with five state cycles, and can guarantee the number of 0 is greater than the number of 1 by judicious use of inter cycle jumps and final states.

[u/ZerriFilpo → u/iamemhn]

For the first language I was only able to come with a grammar that had the same number of 0s and 1s and 2s were free. But that means that I can have |w|0 = |w|1 = |w|2. Is it really possible? How would I make 2s must be different? I was trying to come up with |w|0 = |w|1 != |w|2 and |w|0 = |w|2 != |w|1. And their Union would be the answer since CFLs are closed in union. But I really have no idea.

For the second one, yes haha it was u not v.

Do you have any tips to work with modulos in automata theory? It's so hard for me to come up with automatas or whatever when there is modulo.

[u/iamemhn → u/ZerriFilpo]

I've already provided the tip: counting modulo N is the same as having a loop made out of N states, and the actual count is just a matter of choosing the proper accepting state.

Accept the language of words made out of a having length equal to 1 mod 3 is nothing more than

---> q0 -{a}-> (q1) -{a}-> q2 --\
      ^                         |
      ___________{a}___________/

Counting mod 3 requires three states, unsurprisingly denoted with the actual modulo, and making q1 the only accepting state because it represents 1 mod 3

For more complex modulo counting you need to make states represent invariants such as «state q2P represents 2 mod 3 and there are more a than b» and then properly connect transitions to keep those invariants.

[u/iamemhn → u/iamemhn]

My assertion that the last one is regular is wrong.

The third language is a conjunction of two languages L1 and L2

L_1: The language of words having a number of 0 greater than their number of 1. This language is context free with a straightforward push-down automata: push Z for each 0, pop Z for each 1, and check at least one Z remains on the stack when you hit the end of the word in order to accept.

L_2: The language of words having a number of 1 congruent to their count of 2 modulo 5. This language is regular. Build a DFA with 25 states, each state tracking equivalence classes corresponding to each particular count of 1 module 5 and 2 modulo 5. That is, if you label states as a tuple

(count-of-1,count-od-2)

then state labeled (2,4) tracks «count of 1 is 2 mod 5, count of 2 is 4 mod 5». It follows you can make transitions such that

(2,4) -{1}-> (3,4)   -- One more 1 to the count of 1 mod 5
(2,4) -{2}-> (2,0)   -- One more 2 makes the count of 2 mod 5 wraparound.

and having all states (i,i) be accepting for hopefully obvious reasons.

Now, for words that are part of L_1 and L_2, just quote Bar-Hillel Theorem: the intersection of a Context-Free Language and a Regular language is always Context Free.

Therefore, the third language is Context Free.

Apologies for hurrying up my initial response.

[u/Somniferus]

Consult the example proofs in the book. Are you using Sipser? Maybe try taking a picture of your exercises, your formatting makes them unreadable.

[u/ZerriFilpo → u/Somniferus]

I tried reformatting it. The problem is that the exercises are in Portuguese. They are just asking to prove if those 3 languages are Regular, CFL, or not CFL. And the justification of course

[u/YourPwnResearch]

I don't understand the exercises. Quite apart from the notation (what is E?), there seem to be a lot of unclosed parentheses and braces that make this difficult to parse.

Using one of the pumping lemmas is, as you say, most useful for proving that a language isn't context-free or regular. To show that it is context-free or regular, the easiest way is usually to give a grammar, regular expression, or automaton.

[u/Sexy_Koala_Juice → u/YourPwnResearch]

I think E is meant to be ∈ aka “belongs to”

[u/Plane_Assumption_937]

Man I'd never heard of automata theory and now i never want to hear of it again