patternMinor
Language Recognition Devices and Language Generators
Viewed 0 times
recognitionlanguagedevicesandgenerators
Problem
I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses just like the text books I have.
My question is about language recognizers verses generators.
I get the overriding principle of a recognizer. That it analyses a language and is able to determine nay or yay if a String belongs to a language. This is at least what I have picked up from the books and notes. However, it's much more complex than that is it not? A tokeniser and syntax analyzer (which I assume to be recognizers) do not just say yes or no, they also say where and somtimes what don't they...?
However, regarding language generators,I cannot find a very clear explination about what they are. The typical description I get is, for example in Sebasta's Concepts of programming languages says 'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed.' Seriously? That's it?? Your kidding right....
I read that Regex is an example of a Generator, then why when people talk of generators to they not talk of the inputs. For example Regex has a target String, and the Regex with defines both the accepted alphabet and it's grammar rules.
Can someone provide for me a clearer distinction of what a recogniser is?
My question is about language recognizers verses generators.
I get the overriding principle of a recognizer. That it analyses a language and is able to determine nay or yay if a String belongs to a language. This is at least what I have picked up from the books and notes. However, it's much more complex than that is it not? A tokeniser and syntax analyzer (which I assume to be recognizers) do not just say yes or no, they also say where and somtimes what don't they...?
However, regarding language generators,I cannot find a very clear explination about what they are. The typical description I get is, for example in Sebasta's Concepts of programming languages says 'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed.' Seriously? That's it?? Your kidding right....
I read that Regex is an example of a Generator, then why when people talk of generators to they not talk of the inputs. For example Regex has a target String, and the Regex with defines both the accepted alphabet and it's grammar rules.
Can someone provide for me a clearer distinction of what a recogniser is?
Solution
For a language $L$, a recognizer of $L$ is an algorithm that computes
$\qquad \chi_L(w) = \begin{cases} 1, & w \in L \\ 0 , &w \not\in L\end{cases}$.
Note that in computability and complexity theory, these are sometimes called deciders and algorithms that compute
$\qquad \tilde\chi_L(w) = \begin{cases} 1, & w \in L \\ \uparrow , &w \not\in L\end{cases}$
are called acceptors.
A generator or enumerator can be modelled as an algorithm computing
$\qquad e_L(i) = w_i$
where $L = \{ w_i \mid i \in \mathbb{N} \}$. As it turns out, $e_L$ and $\tilde\chi_L$ are equal in power (cf. the set of recursively enumerable languages) but $\chi_L$ is stronger (cf. the set of recursive/decidable languages).
You typically want compilers to be deciders; interpreters are arguably recognisers.
A regular expression (or, for that matter, a grammar) does not fit in this terminology per se. I'd say they give a descriptive representation of their languages while above notions are algorithms representatios. Grammars have a slighly more enumerative feel (since translating them into a top-down generator of words is intuitive) while regular expressions feel more like deciders (via their NFA), but it's also easy to build acceptors from grammars.
$\qquad \chi_L(w) = \begin{cases} 1, & w \in L \\ 0 , &w \not\in L\end{cases}$.
Note that in computability and complexity theory, these are sometimes called deciders and algorithms that compute
$\qquad \tilde\chi_L(w) = \begin{cases} 1, & w \in L \\ \uparrow , &w \not\in L\end{cases}$
are called acceptors.
A generator or enumerator can be modelled as an algorithm computing
$\qquad e_L(i) = w_i$
where $L = \{ w_i \mid i \in \mathbb{N} \}$. As it turns out, $e_L$ and $\tilde\chi_L$ are equal in power (cf. the set of recursively enumerable languages) but $\chi_L$ is stronger (cf. the set of recursive/decidable languages).
You typically want compilers to be deciders; interpreters are arguably recognisers.
A regular expression (or, for that matter, a grammar) does not fit in this terminology per se. I'd say they give a descriptive representation of their languages while above notions are algorithms representatios. Grammars have a slighly more enumerative feel (since translating them into a top-down generator of words is intuitive) while regular expressions feel more like deciders (via their NFA), but it's also easy to build acceptors from grammars.
Context
StackExchange Computer Science Q#22288, answer score: 7
Revisions (0)
No revisions yet.