f



Why the characterisitic language of a CFG is regular?

Hi!

I've seen in the most of the compiler texts that the viable prefixes of
a CFG form a regular language.Then they attempt to build DFA/NFA for recognizing
this language, but the don't give a proof or an intuition why this language
is regular.Does anyone have an idea about the reason of this regularity?

Thanks

  Hossein Hojjat
 Tehran University,
Institute of Electrotechnique
0
7/2/2003 4:36:29 AM
comp.compilers 3310 articles. 1 followers. Post Follow

0 Replies
1082 Views

Similar Articles

[PageSpeed] 41

Reply:

Similar Artilces:

is the language of regular expressions a regular language?
The set REX of regular expressions over the alphabet {a, b} is itself a language over the alphabet {e,0 , a, b, ), (*,U, .} is this language regular? I want to say yes, however, I am not sure what approach to take? Which would be easiest? Construct a DFA or a regular expression? Or am I wrong and this language is not regular? TheGist writes: > The set REX of regular expressions over the alphabet > {a, b} > is itself a language over the alphabet > {e,0 , a, b, ), (*,U, .} > > is this language regular? > > I want to say yes, however, I am not sure what approac...

separating context-free languages by regular languages
Give two disjunct context-free languages L1, L2 so that there is no pair of disjunct regular languages (R1,R2) with Li subset Ri (i=1,2). I would be glad for any references or ideas. Thanks a lot, sasha. Is disjunt same as disjoint? I assume it is required that none of the Ri's are empty (otherwise trivial choice of R1=Z^*, R2={} ensures non-existance of such Li pairs. Z is the set of alphabets) Now, a necessary and sufficient condition for such a pair of Li's is that L1 is non-regular CFL and L2=Z^*\L1 is CFL. If L1 and L2 are two CFLs such that there is no pair R1,R2 of RLs suc...

writing a compiler for Monster language using C language
hi, i have to write a compiler for Monster language using C.example programs of the language are: EXAMPLE 1 /* Test Program - Module Structure */ module fact export N2N; export fact; type N2N is -> int ret int throws; val fact : N2N; fact := fun(n) { if n=0 then return 1 else return n*fact(n-1); }; end module main import fact.N2N; import fact.fact; type TLF is -> int ret throws; val x:int; val main : TLF; main := fun(n) { val result:int; result:= fact(n); print result; }; end EXAMPLE 2 module Stack export Stack; type OverFlowException is * errMsg : str * size : int; t...

Compile Time Programming, why not Compile Time Functional Language?
I am currently reading "Modern C++ Design" and have aspirations of eventually reading the Vandervorde book which currently takes pride of place on my desk at work to strike a chill of terror into my friends... Something however that I feel is left un-answered and even un-addressed by the peers of c++. Why doesnt compile time programming for c++ utilise a proper programming language in itself? For instance imagine being able to manipulate the abstract syntax tree of a c++ program using a Haskell like language. Wouldn't the degree by which people could utilise the techniques of...

To compile or not to compile
Is there some benefit in compiling the apache source yourself? -- //Points ------------------------------------------------------------ http://underthebed.homeip.net ...

To compile or not to compile
Is there some benefit in compiling the apache source yourself? -- //Points ------------------------------------------------------------ http://underthebed.homeip.net ...

cfg for this language
Can someone give a cfg for L = {xcy | x!=(reverse of y), (x, y in {a, b}*) } thanks. In article <1140620446.587574.96310@g44g2000cwa.googlegroups.com>, "kool_guy" <yjaplomb@gmail.com> writes: > Can someone give a cfg for > > L = {xcy | x!=(reverse of y), (x, y in {a, b}*) } S = aSa | bSb | C C = aBcBb | bBcBa | ABc | cBA B = | AB A = a | b -- Heiner Marxen http://www.drb.insel.de/~heiner/ You really should do your own homework, "kool guy" Hi lintile, Knowledge expands by sharing it, have you ever heard of it? I am studying for my mid-te...

A Compiler for Natural Language (transator that translates from natural language to C++)
Hi, I got very good response for the C++ intermediate representation. And thanks to all the experts. Now i need some help for one project I am doing as a part of my study. Well it may sound a bit off track but the idea is to desing a compiler that learns language like human learn. I am explaining my idea little bit. This compiler is a natural language system That is near to an expert system. The aim of the system is to convert natural language statements into C++ (or any other language,but we need to feed that language structure into this application). We train the compiler to the destination...

Regular Languages
Hi everybody, Is it possible to represent each regular language with a planar NFA graph? Cheers, Behrang. On 25 Jan 2004, Behrang wrote: > Is it possible to represent each regular language with a planar NFA graph? Interesting question... my suspicion is no. Consider an alphabet S = {0,1,2,3,4} and a language L = {w in S* such that the sum of the characters of w is 0 mod 5} Then any machine would need states representing (at least) the five possible current sums (mod 5) and since any symbol (0 through 4) could move the action from one state to any other state, there has be som...

a language is a language
Okay, I've seen some comments here and in other groups about languages. Here's the question: What constitutes a programming language? Examples to consider C Assembler SQL PERL HTML PL/SQL Postscript Jscript bash runoff, pic, eqn JCL BASIC RTL (Register Transfer Language) Excell (yes the spreadsheet) ORACLE FORMS What do you consider a programming language and why? (I really want to hear some thoughtful justification rather than just "that's my view" posts.) I'll post my views a little later. Ed "Ed Prochak" <edprochak@gmail.com> writes: > Ok...

which compiler compiled?
Is there a way I can tell which compiler compiled an executable? I looked at the file with a hex editor and didn't see anything obvious. Lawrence "Lawrence" <just4me@nowhere.com> writes: > Is there a way I can tell which compiler compiled an executable? Yes with some compilers and some executable formats. E.g. on HP-UX for PA-RISC: $ aCC leak.C $ odump -compunit a.out ... 6 0 ANSI C++ leak.C /tmp ctcom options = -inst compiletime -diags 523 -inline_power 1 -longbranch 2 -unique_strings on -cachesize 256 B...

Compiled or not compiled
I need to distinguish between two situations: one when a Matlab function is run from Matlab command window and the other one when it is run in compiled mode. Any ideas how to do this? Thanks Tomy Duby "Tomy Duby" <tomy.duby@agilent.com> wrote in message news:idq8q8$85k$1@fred.mathworks.com... > I need to distinguish between two situations: one when a Matlab function > is run from Matlab command window and the other one when it is run in > compiled mode. > Any ideas how to do this? HELP ISDEPLOYED. -- Steve Lord slord@mathworks.com comp.s...

Compile or not compile?
There's something that sometimes in while it bores me a little bit. How do I know if I need to compile a function/procedure or it will be able to compile "on fly". At the beginning I thought this was related to the paths idl "knew", but this happens for two functions/routines in the same directory. Can someone tell when a function can be runned without be compile? Nuno Oliveira wrote: > There's something that sometimes in while it bores me a little bit. How > do I know if I need to compile a function/procedure or it will be able > to compile &quo...

Compiling Compiler
Hi there, I need some advice/opinion of the experts out there regarding compilers. I have sun cc compiler that supports 64 bit environment. Now, I compile ACK using this compiler.This should give a compiler that supports 64bit environment. Since the output files are in Solaris format, I compile the ACK source *once again* using the just compiled ACK compiler so that I get Minix object and binary files. Now my questions is that does this 2nd version of ACK be able to produce true 64bit code? Sanky wrote: > Hi there, > > I need some advice/opinion of the experts out there regarding...

Web resources about - Why the characterisitic language of a CFG is regular? - comp.compilers

Alliant Powder - About Us
Every container of Alliant smokeless powder is backed by a century of manufacturing experience and the most exacting quality control procedures ...

The Privatization Programs in Russia in the 1990's
... understood the importance of not trying to micromanage or to secondguess on the work of his subordinates. One of Chubais' characterisitics wasto ...

Yesterday: "Last Throes"; Today: "We Cannot Predict the Length..."
« Department of Short-Sighted 'Leveraging' Strategies - Main - Partitioning Iraq Is Still a Bad Idea » August 17, 2005 Yesterday: "Last Throes"; ...

BRONY STUDY (Research Project)
Reason for the Study: Recently we have become aware that there is a new phenomenon emerging, primarly among adolescent and young adult males. ...

Steady Realism – The Forgotten Trait for Entrepreneurs
Every so often a magazine or a book contains a list of "Top Five Traits of Entrepreneurs" or "Top Ten Signs of a Good Leader." I have nothing ...

Samsung’s New TV Enables Two Viewers To Watch Different Shows Simultaneously
... off in addition to a voice command feature it calls S-Recommendation: Users can use natural language to ask for different programming characterisitics, ...

Re: Spotify Users Are Twice as Likely to Purchase a Download...
Be careful about the conclusions you draw from this. This data DOE NOT SAY: Being a user of Spotify INCREASES your probability of buying music. ...

Slideshow: Osteoporosis - Are Your Bones at Risk?
Low bone mass and density may leading to weak, thin and fragile bones are characterisitics of the disease Osteoporosis. View this slideshow to ...

swanson model - ft - sport plane - 1923 - 0261 - Flight Archive
MAY 17, 1923 THE SWANSON MODEL 3 SPORT 'PLANE THE little sporting biplane shown in the accompanying illustrations was designed and constructed ...

Makers of Modern Strategy: From Machiavelli to the Nuclear Age - Google Books
The essays in this volume analyze war, its strategic characterisitics and its political and social functions, over the past five centuries. The ...

Resources last updated: 1/24/2016 6:37:07 AM