Theory of computation - Using the pumping lemma for CFLs

Posted by Tony on Stack Overflow See other posts from Stack Overflow or by Tony
Published on 2010-04-11T16:14:57Z Indexed on 2010/04/11 16:23 UTC
Read the original article Hit count: 307

Filed under:

context-free-grammar

|

homework

I'm reviewing my notes for my course on theory of computation and I'm having trouble understanding how to complete a certain proof. Here is the question:

A = {0^n 1^m 0^n | n>=1, m>=1}  Prove that A is not regular.

It's pretty obvious that the pumping lemma has to be used for this. So, we have

|vy| >= 1
|vxy| <= p (p being the pumping length, >= 1)
uv^ixy^iz exists in A for all i >= 0

Trying to think of the correct string to choose seems a bit iffy for this. I was thinking 0^p 1^q 0^p, but I don't know if I can obscurely make a q, and since there is no bound on u, this could make things unruly..

So, how would one go about this?

© Stack Overflow or respective owner

Related posts about context-free-grammar

Parsing a context-free grammar in Python

as seen on Stack Overflow - Search for 'Stack Overflow'
What tools are available in Python to assist in parsing a context-free grammar? Of course it is possible to roll my own, but I am looking for a generic tool that can generate a parser for a given CFG. >>> More
Convert The Context Free Grammar to LL1 Grammar

as seen on Stack Overflow - Search for 'Stack Overflow'
hi I want to write a program to gives grammar as input and change it to LL1. my problem is converting to LL1 I don't have any algorithm to convert. I earn grammar from some input text by a simple text analyzer but how I can change it to LL1 ? is there any algorithm that is clear to implement. >>> More
Efficient Context-Free Grammar parser, preferably Python-friendly

as seen on Stack Overflow - Search for 'Stack Overflow'
I am in need of parsing a small subset of English for one of my project, described as a context-free grammar with (1-level) feature structures (example) and I need to do it efficiently . Right now I'm using NLTK's parser which produces the right output but is very slow. For my grammar of ~450 fairly… >>> More
"Arbitrary" context free grammars?

as seen on Stack Overflow - Search for 'Stack Overflow'
Long time admirer first time inquirer :) I'm working on a program which derives a deterministic finite-state automata from a context-free grammar, and the paper I have been assigned which explains how to do this keeps referring to "arbitrary probabilistic context-free grammars" but never defines… >>> More
What does "context-free" mean in the term "context-free grammar"?

as seen on Programmers - Search for 'Programmers'
Given the amount of material that tries to explain what a context-free grammar (CFG) is, I found it surprising that very few (in my sample, less than 1 in 20) give an explanation on why such grammars are called "context-free". And, to my mind, none succeeds in doing so. My question is, why are context-free… >>> More

Related posts about homework

parsing a list and producing a structure of that

as seen on Stack Overflow - Search for 'Stack Overflow'
;; structure representing homework points ;; nr: number - the number of the homework ;; points: number - the number of points reached (define-struct homework (nr points)) ;; parse-homework: (list of number pairs) -> (list of homework) ;; The procedure takes a list of number pairs and produces… >>> More
Scheme homework help

as seen on Stack Overflow - Search for 'Stack Overflow'
Okay so I have started a new language in class. We are learning Scheme and i'm not sure on how to do it. When I say learning a new language, I mean thrown a homework and told to figure it out. A couple of them have got me stumped. My first problem is: Write a Scheme function that returns true (the… >>> More
Unix [Homework]: Get a list of /home/user/ directories in /etc/passwd

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm very new to Unix, and currently taking a class learning the basics of the system and its commands. I'm looking for a single command line to list off all of the user home directories in alphabetical order from the /etc/passwd directory. This applies only to the home directories, and not the contents… >>> More
sequential search homework question

as seen on Stack Overflow - Search for 'Stack Overflow'
Consider a disk file containing 100 records a. How many comparisons would be required on the average to find a record using sequential search, if the record is known to be in the file? I figured out that this is 100/2 = 50. b. If the record has a 68% probability of being in the file, how many comparisons… >>> More
[Homework] Online programming editor

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, For a school project i need to write or use a online programming editor. It is a part of a bigger project. I thought of a java application, php/html/javascript or flash. I have a couple of things i could do: Find a good working application and edit it so it works with the rest of the project Find… >>> More