Would this be context free or regular

[a_1_a_5]

Strings over the alphabet {a,b,c,d} where there are at least 3 times as many b's as c's

[tliff]

Sounds a bit like homework:

What usually helped me: look at the problem and see if you can build an automaton that can perform that check.

Context-free languages are as expressive as pushdown automata and regular grammars are as expressive as finite state machines.

[Yakk]

You could also pump out the (appropriate) pumping lemma. That is one of the more powerful tools for proving something isn't in a particular category. It isn't always that useful to guess what category something belongs to... but it is a tool.

You can also simplify, using language-intersection to make the problem simpler. (If you take a language and intersect it with a Regular language, and prove the result isn't Regular, what does that let you know?)

[a_1_a_5]

well the way i have done it...I get a context free grammar.Bit I wanna confirm that I've done it correctly.

[Yakk]

You could
A) Type out your answer, and ask for opinions and/or a critique.
B) When people who you are asking for help ask you questions, you could answer them.
C) Beg for someone to give you an answer, and otherwise do not interact.

You have chosen: C

[a_1_a_5]

when i did this i made a context free grammar....and that seemed to work because i really
couldn't come up with a regular expression. Although i'm sure there are regular expressions for this....so now i'm not sure which one it is.

[Yakk]

I'm assuming this is for an "introduction to computer science" or "introduction to the theory of computation" course or something.

So have you even heard of the pumping lemma? Do you know what happens when you intersect a regular language with another regular language?

Have you seen a proof that "a^n b^n" is not a regular language? Can you prove that a^n b^n is not a regular language?

Every language that is regular also has a context free grammar. To show that a language isn't regular, it takes more work than coming up with a context free grammar!

[a_1_a_5]

that really...doesn't help...all im asking is if im on the right track...when i say that it is a context-free and not a regular language. And for the record yes i do know that.

[headprogrammingczar]

You have a CFG for your language already. There's a way to transform some CFGs into regexes (more accurately, a way to transform a regex into a CFG, but the process is reversible). If you can't, your language isn't regular.

(this trick might not count as showing your work)

[Yakk]

Really? You cannot write a regular grammar that cannot be converted via mechanical operations to a RE for a regular language?

I'm surprised!

[a_1_a_5]

Well the way I came up with it I don't there I can transform this is not a regex...therefore I conclude that it is a CFG and is not regular.

[Yakk]

I actually (edit:) doubt that head programming czar is correct. I'm uncertain, but I doubt it is correct. If you are asking for homework help, and you made the claim headprogrammingczar made without at least a reference to a theorem, or a proof it is true, I'd give you about 2 or 3/10 on the question for finding a CFG that matches the language.

[EvanED]

I also doubt it's correct as well. In fact, I doubt it so much that I asked on the CS theory stack exchange. I would wager some small amount of money that it is not decidable whether a language defined by a CFG is regular if I knew any of you in real life.

Edit: "Greibach’s theorem can be used to show that it is undecidable whether a context-free grammar generates a regular language."

[a_1_a_5]

This is what I get for the CFG for this...can anyone help please...

[Laguana]

Something I always find helpful when working with grammars is to try to break them. For example, I can prove that the CFG you give there is incorrect, since it allows for this string:

c e

which obviously has 1 > 3*0 occurrences of c.


What everyone was saying earlier is more important though: Constructing a CFG will be unhelpful. You need to be able to either a) produce a regular grammar, proving that the language is regular, or b) prove that you are unable to produce a regular grammar, and that the language is not regular.

[a_1_a_5]

oh sorry the previous one is in terms of where there are at least 3 times more a's than b's

[a_1_a_5]

which is still incorrect...just noticed...can anyone give me hints as how to fix this....

[Laguana]

What things do you know about regular languages and context free languages? What theorems do you know? What ways of proving them do you know?

Without knowing where you are working from, we can't really help you. I could say "Of course this language is regular, it is obvious", but that doesn't help anyone.

[a_1_a_5]

whatt its...regular....??

[headprogrammingczar]

Really? You cannot write a regular grammar that cannot be converted via mechanical operations to a RE for a regular language?

I'm surprised!

What I meant was, if you write a CFG that happens to also be regular, there's a mechanical way to transform back to a regex. If that mechanical method doesn't work, your CFG wasn't regular to begin with.

Sorry if I derailed the thread.

[Laguana]

whatt its...regular....??

I could also say "Of course it isn't regular, it's obvious", and be equally unhelpful. My point is without a proof (and you haven't said what proof tools you have available) then claims are useless.

[jareds]

Really? You cannot write a regular grammar that cannot be converted via mechanical operations to a RE for a regular language?

I'm surprised!

What I meant was, if you write a CFG that happens to also be regular, there's a mechanical way to transform back to a regex. If that mechanical method doesn't work, your CFG wasn't regular to begin with.

I'm not sure I understand the distinction. Are you saying that, for any CFG of a regular language, the algorithm definitely succeeds, but for a CFG of a non-regular language, the algorithm might fail rather than returning "non-regular", such as by returning a regular expression (which would therefore be wrong), or by non-termination? That is the only way that your claim is not contradicted by the theorems cited by EvanED, but I still find it difficult to believe.

Sorry if I derailed the thread.

Don't be silly! You're a good forum member who sparked a bona fide CS tangent. In contrast, the main reason that the original point of the thread isn't making progress is that the OP is simply begging or fishing for homework answers or hints without a even a minimal effort at interaction such as responding to repeated requests to explain what he does or does not know or understand.