Most voted "formal-languages" questions
11 questions
Sort by count of
-
31
votes2
answers5048
viewsWhat is a context-free language?
In Wikipedia has the following statement: In formal language theory, a context-free language (LLC) is a language generated by some context-free grammar (GLC). Different context-free grammars can…
terminology computer-science computer-theory formal-languagesasked 7 years, 9 months ago viana 27,141 -
23
votes1
answer1194
viewsRegular expression to recognize language: words that do not contain "bbab"
The @LINQ challenged me to write a regular expression to recognize the following language L: I was able to assemble, on this premise, the following finite state machine: the Miguel Angelo detected a…
regex mathematics computer-theory automata formal-languagesasked 7 years, 1 month ago Jefferson Quesado 22,370 -
15
votes1
answer229
viewsIs a finite state machine capable of detecting the primality of a number?
I recently saw a publishing how they taught Perl to recognize a prime number using regular expressions. The regular expression in question is: /^1?$|^(11+?)\1+$/ The only requirement of this regular…
regex mathematics computer-theory automata formal-languagesasked 4 years, 9 months ago Jefferson Quesado 22,370 -
6
votes1
answer66
viewsA subset language of a context-free language is decidable?
If we have a context-free language L and L' is a subset of L, then L' is decidable?
-
5
votes1
answer425
viewsWhat is the Pumping Lemma (or Pumping Lemma) ? And how to apply it?
I was reading by HOPCROFT and had difficulty applying the pumping lemma in a formal way to exercises to prove that a language is not regular. In this case, I refer to the Pumping Motto for regular…
-
5
votes1
answer1014
viewsDifference between 'Regular language' for 'irregular language'
Reading a question about basic programming concepts, I come across the following statement: Let A and B be two languages over the binary alphabet, that is, over the alphabet composed only of 0’s and…
computer-science computer-theory automata formal-languagesasked 5 years, 10 months ago Luiz Augusto 2,482 -
4
votes1
answer326
viewsReduce grammars in the Chomsky hierarchy
I know from Chomsky’s hierarchy, all regular grammar is also a context-free grammar. Similarly, I know that a context-free grammar is also a context-sensitive grammar and etc. I’d like to know how…
-
3
votes1
answer1775
viewsHow to turn a context-free grammar into a stack automaton?
I have a grammar, like for example: Or else: Or even that: Or this grammar, which represents the boolean logic for three variables: How to turn these grammars into stack automata? Would have some…
algorithm computer-theory automata formal-languagesasked 7 years, 1 month ago Jefferson Quesado 22,370 -
3
votes1
answer775
viewsDoubt about Chomsky’s hierarchy
Regarding the 4 types of languages, I doubt to understand about context-dependent or context-sensitive language. I find very confusing the explanation that I find through the sites, I would like…
-
0
votes2
answers69
viewsI need a parser-building tool
So, first I need a parse building tool, I don’t know exactly what it is and where I think, if possible preferably in the Python language. I will use this tool in order to implement an expression…
-
-1
votes1
answer55
viewsQuestions about Backus Naur Form
I’m having second thoughts about the BNF exercises. Write a BNF to generate sequences of binary digits in pairs for example: 0 0 11 0 0, 11 00 1 1 , 1 1 1 0 0 1 1 Write a BNF to generate sequences…
formal-languagesasked 4 years, 8 months ago Thais Monteiro 1