Improve company productivity with a Business Account.Sign Up

x
?
Solved

Context free grammar

Posted on 2011-02-23
2
Medium Priority
?
342 Views
Last Modified: 2012-05-11
Hello experts,
How I will translate a regular expression which contains a group of characters to cfg?
For example if I have this regular expression:
[wx]*ocl(qw|zx)*
how I will translate this?
And also how I will define a cfg which will  not let me define this regular expression using bracketing?
0
Comment
Question by:puffyy_beginner
  • 2
2 Comments
 
LVL 13

Accepted Solution

by:
Superdave earned 2000 total points
ID: 34962101
1.  Could you clarify whether this is your homework?
2.  I don't understand the second question.  Are you asking for a CFG that is not an RE?
0
 
LVL 13

Expert Comment

by:Superdave
ID: 34962159
Anyway, you can use "recursion" in a production to make something repeat:

wx ::= "w"|"x"
wxstar := "" | (wx wxstar)
 

If I guessed right about what your second question meant, having a language with the rule that you have the same number of a repeating character in two places is a typical example of a CFG that is not regular.  I'll let you work out the grammar for it until I find out about my first question.
0

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

When you see single cell contains number and text, and you have to get any date out of it seems like cracking our heads.
What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
Progress
Starting up a Project

595 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question