Stack Overflow
Stack Overflow

Questions tagged [context-free-language]

In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). The set of regular languages is a subset of the set of context-free languages.

183 questions
19
votes
3 answers

The difference between Chomsky type 3 and Chomsky type 2 grammar

I'm having trouble articulating the difference between Chomsky type 2 (context free languages) and Chomsky type 3 (Regular languages). Can someone out there give me an answer in plain English? I'm having trouble understanding the whole hierarchy…
Jay Jenkins
  • 413
  • 1
  • 5
  • 15
5
votes
1 answer

CFG of Language which contains equal # of a's and b's

I've tried this S -> e(Epsilon) S -> SASBS S -> SBSAS A -> a B -> b Can someone verify if this is correct.
Adnan Qureshi
  • 546
  • 1
  • 6
  • 16
5
votes
1 answer

Example of a recursively enumerable language that is not context free

What is a simple example of a recursively enumerable language that is not context free? My textbook is awful in providing such an example explicitly. To be clear this isn't a hmk question.
Bren
  • 3,516
  • 11
  • 41
  • 73
5
votes
1 answer

Can extended Backus Naur Form (EBNF) describe an unordered set of values?

I'd like to define an unordered set of values using an Extended Backus-Naur Form (EBNF) context free grammar. It's easy to define an unordered list of values in EBNF, for example: value = 'A' | 'B' | 'C'; list = value, {',', value}; However, I'm…
LostInTheWeb
  • 187
  • 1
  • 11
5
votes
1 answer

Deterministic Context-Free Grammar versus Context-Free Grammar?

I'm reading my notes for my comparative languages class and I'm a bit confused... What is the difference between a context-free grammar and a deterministic context-free grammar? I'm specifically reading about how parsers are O(n^3) for CFGs and…
Laurence
  • 157
  • 1
  • 2
  • 10
5
votes
1 answer

intersection of two context-free languages

I'm having some trouble understanding how to get the intersection of two context-free languages (L = L1 ∩ L2). I've seen the very common example where: L1 = {a^i b^i c^j | i,j ≥0} L2 = {a^i b^j c^j | i,j ≥0} L1 ∩ L2 = {a^i b^i c^i | i ≥0} but…
user2256498
  • 85
  • 1
  • 8
4
votes
1 answer

Can regex be used to recognize any Context Free Language?

I know that regex packages can recognize a wider set of languages than just Regular Languages, but the use of recursive regex in Python regex to find arithmetic expressions in text strings makes me wonder if it is possible to recognize any Context…
Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
4
votes
1 answer

How to prove the correctness of a given grammar?

I am wondering how programming langauge developers validate and prove that their grammar is correct. Suppose that I created a new grammar for a new langauge. I can test my grammar with a unit test tool by providing different kinds of test programs.…
Barış Akkurt
  • 2,255
  • 3
  • 22
  • 37
4
votes
1 answer

Is WW where W belongs to {a,b}* a context free language?

Is WW where W belongs to {a,b}* a context free language? If yes, please provide the PDA for it.
Sanat Deshpande
  • 186
  • 1
  • 1
  • 8
4
votes
1 answer

How can I tell that a language is context-free from first sight?

My professor expects us to quickly tell if a given language is regular, context-free but not regular, or not context-free (in other words, without drawing a PDA, writing a context-free grammar, and using the pumping lemma for context-free…
John
  • 53
  • 1
  • 3
4
votes
2 answers

Is it a right way to find the regular grammar by construct an DFA?

This is my homework. Exercise 3: Find a regular grammar for the language L = { | n + m is an odd number}. Show the way you obtain it. The question ask to show the way I obtain the answer. So here is my explain. We construct the DFA From DFA,…
Haha TTpro
  • 5,137
  • 6
  • 45
  • 71
4
votes
1 answer

Is the language to describe regular expressions regular itself?

If we describe regular expressions with operators *, | and concatenation . (which we simply omit for clarity), and parenthesis (, ) and some letters from some alphabet Sigma, then is the language that describes regular expressions itself regular? In…
baibo
  • 448
  • 4
  • 20
4
votes
3 answers

concatenation & union - regular and context free languages

Given L1 context free non regular language. Given L2 regular language. Is it possible that L1 U L2 = regular language ? Also, is it possible that L1*L2 = regular language ? I think that the 2nd one is impossible. But I'm not sure. Would love to see…
Rouki
  • 2,239
  • 1
  • 24
  • 41
4
votes
1 answer

Union of two (irregular) Context Free Language results a Regular Language?

Given L1 and L2 (irregular) context free languages - Is it possible that L1 U L2 is regular? I know that it is possible but I just cant find an example showing that. Would love to get some assistance.
Rouki
  • 2,239
  • 1
  • 24
  • 41
3
votes
1 answer

Functional Programming Binary Search Tree Homework

So I am having to write an insert function for a binary tree to make it a binary search tree, but I'm having some trouble. Everything is functions, so I understand that there is no concept of a state. Therefore, I need to recursively create the tree…
Some Guy
  • 351
  • 1
  • 4
  • 20
1
2 3
…
12 13