Solved

Context free grammar

Posted on 2011-02-23
2
303 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 500 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

A short article about a problem I had getting the GPS LocationListener working.
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

910 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now