text:
Geochemistry

Geochemistry is the science that uses the tools and principles of chemistry to explain the mechanisms behind major geological systems such as the Earth's crust and its oceans. The realm of geochemistry extends beyond the Earth, encompassing the entire Solar System, and has made important contributions to the understanding of a number of processes including mantle convection, the formation of planets and the origins of granite and basalt. It is an integrated field of chemistry and geology.

History
The term geochemistry was first used by the Swiss-German chemist Christian Friedrich Schönbein in 1838: "a comparative geochemistry ought to be launched, before geognosy can become geology, and before the mystery of the genesis of our planets and their inorganic matter may be revealed." However, for the rest of the century the more common term was "chemical geology", and there was little contact between geologists and chemists.

Geochemistry emerged as a separate discipline after major laboratories were established, starting with the United States Geological Survey (USGS) in 1884, which began systematic surveys of the chemistry of rocks and minerals. The chief USGS chemist, Frank Wigglesworth Clarke, noted that the elements generally decrease in abundance as their atomic weights increase, and summarized the work on elemental abundance in The Data of Geochemistry.

The composition of meteorites was investigated and compared to terrestrial rocks as early as 1850. In 1901, Oliver C. Farrington hypothesised that, although there were differences, the relative abundances should still be the same. This was the beginnings of the field of cosmochemistry and has contributed much of what we know about the formation of the Earth and the Solar System.

In the early 20th century, Max von Laue and William L. Bragg showed that X-ray scattering could be used to determine the structures of crystals. In the 1920s and 1930s, Victor Goldschmidt and associates at the University of Oslo applied these methods to many common minerals and formulated a set of rules for how elements are grouped. Goldschmidt published this work in the series Geochemische Verteilungsgesetze der Elemente [Geochemical Laws of the Distribution of Elements].

The research of Manfred Schidlowski from the 1960s to around the year 2002 was concerned with the biochemistry of the Early Earth with a focus on isotope-biogeochemistry and the evidence of the earliest life processes in Precambrian.

Subfields
Some subfields of geochemistry are:
 * Aqueous geochemistry studies the role of various elements in watersheds, including copper, sulfur, mercury, and how elemental fluxes are exchanged through atmospheric-terrestrial-aquatic interactions.
 * Biogeochemistry is the field of study focusing on the effect of life on the chemistry of the Earth.
 * Cosmochemistry includes the analysis of the distribution of elements and their isotopes in the cosmos.
 * Isotope geochemistry involves the determination of the relative and absolute concentrations of the elements and their isotopes in the Earth and on Earth's surface.
 * Organic geochemistry, the study of the role of processes and compounds that are derived from living or once-living organisms.
 * Photogeochemistry is the study of light-induced chemical reactions that occur or may occur among natural components of the Earth's surface.
 * Regional geochemistry includes applications to environmental, hydrological and mineral exploration studies.

Chemical elements
The building blocks of materials are the chemical elements. These can be identified by their atomic number Z, which is the number of protons in the nucleus. An element can have more than one value for N, the number of neutrons in the nucleus. The sum of these is the mass number, which is roughly equal to the atomic mass. Atoms with the same atomic number but different neutron numbers are called isotopes. A given isotope is identified by a letter for the element preceded by a superscript for the mass number. For example, two common isotopes of chlorine are 35Cl and 37Cl. There are about 1700 known combinations of Z and N, of which only about 260 are stable. However, most of the unstable isotopes do not occur in nature. In geochemistry, stable isotopes are used to trace chemical pathways and reactions, while radioactive isotopes are primarily used to date samples.

The chemical behavior of an atom – its affinity for other elements and the type of bonds it forms – is determined by the arrangement of electrons in orbitals, particularly the outermost (valence) electrons. These arrangements are reflected in the position of elements in the periodic table. Based on position, the elements fall into the broad groups of alkali metals, alkaline earth metals, transition metals, semi-metals (also known as metalloids), halogens, noble gases, lanthanides and actinides.

Another useful classification scheme for geochemistry is the Goldschmidt classification, which places the elements into four main groups. Lithophiles combine easily with oxygen. These elements, which include Na, K, Si, Al, Ti, Mg and Ca, dominate in the Earth's crust, forming silicates and other oxides. Siderophile elements (Fe, Co, Ni, Pt, Re, Os) have an affinity for iron and tend to concentrate in the core. Chalcophile elements (Cu, Ag, Zn, Pb, S) form sulfides; and atmophile elements (O, N, H and noble gases) dominate the atmosphere. Within each group, some elements are refractory, remaining stable at high temperatures, while others are volatile, evaporating more easily, so heating can separate them.

Differentiation and mixing
The chemical composition of the Earth and other bodies is determined by two opposing processes: differentiation and mixing. In the Earth's mantle, differentiation occurs at mid-ocean ridges through partial melting, with more refractory materials remaining at the base of the lithosphere while the remainder rises to form basalt. After an oceanic plate descends into the mantle, convection eventually mixes the two parts together. Erosion differentiates granite, separating it into clay on the ocean floor, sandstone on the edge of the continent, and dissolved minerals in ocean waters. Metamorphism and anatexis (partial melting of crustal rocks) can mix these elements together again. In the ocean, biological organisms can cause chemical differentiation, while dissolution of the organisms and their wastes can mix the materials again.

Fractionation
A major source of differentiation is fractionation, an unequal distribution of elements and isotopes. This can be the result of chemical reactions, phase changes, kinetic effects, or radioactivity. On the largest scale, planetary differentiation is a physical and chemical separation of a planet into chemically distinct regions. For example, the terrestrial planets formed iron-rich cores and silicate-rich mantles and crusts. In the Earth's mantle, the primary source of chemical differentiation is partial melting, particularly near mid-ocean ridges. This can occur when the solid is heterogeneous or a solid solution, and part of the melt is separated from the solid. The process is known as equilibrium or batch melting if the solid and melt remain in equilibrium until the moment that the melt is removed, and fractional or Rayleigh melting if it is removed continuously.

Isotopic fractionation can have mass-dependent and mass-independent forms. Molecules with heavier isotopes have lower ground state energies and are therefore more stable. As a result, chemical reactions show a small isotope dependence, with heavier isotopes preferring species or compounds with a higher oxidation state; and in phase changes, heavier isotopes tend to concentrate in the heavier phases. Mass-dependent fractionation is largest in light elements because the difference in masses is a larger fraction of the total mass.

Ratios between isotopes are generally compared to a standard. For example, sulfur has four stable isotopes, of which the two most common are 32S and 34S. The ratio of their concentrations, $R=^{34}S/^{32}S$, is reported as
 * $$\delta{}^{34}\mathrm{S} = 1000\left(\frac{R}{R_\mathrm{s}}-1\right),$$

where $R_{s}$ is the same ratio for a standard. Because the differences are small, the ratio is multiplied by 1000 to make it parts per thousand (referred to as parts per mil). This is represented by the symbol $‰$.

Equilibrium
Equilibrium fractionation occurs between chemicals or phases that are in equilibrium with each other. In equilibrium fractionation between phases, heavier phases prefer the heavier isotopes. For two phases A and B, the effect can be represented by the factor
 * $$ a_\mathrm{A-B} = \frac{R_\mathrm{A}}{R_\mathrm{B}}. $$

In the liquid-vapor phase transition for water, $a_{l-v}$ at 20 degrees Celsius is 1.0098 for 18O and 1.084 for 2H. In general, fractionation is greater at lower temperatures. At 0 °C, the factors are 1.0117 and 1.111.

Kinetic
When there is no equilibrium between phases or chemical compounds, kinetic fractionation can occur. For example, at interfaces between liquid water and air, the forward reaction is enhanced if the humidity of the air is less than 100% or the water vapor is moved by a wind. Kinetic fractionation generally is enhanced compared to equilibrium fractionation and depends on factors such as reaction rate, reaction pathway and bond energy. Since lighter isotopes generally have weaker bonds, they tend to react faster and enrich the reaction products.

Biological fractionation is a form of kinetic fractionation since reactions tend to be in one direction. Biological organisms prefer lighter isotopes because there is a lower energy cost in breaking energy bonds. In addition to the previously mentioned factors, the environment and species of the organism can have a large effect on the fractionation.

Cycles
Through a variety of physical and chemical processes, chemical elements change in concentration and move around in what are called geochemical cycles. An understanding of these changes requires both detailed observation and theoretical models. Each chemical compound, element or isotope has a concentration that is a function $C(r,t)$ of position and time, but it is impractical to model the full variability. Instead, in an approach borrowed from chemical engineering, geochemists average the concentration over regions of the Earth called geochemical reservoirs. The choice of reservoir depends on the problem; for example, the ocean may be a single reservoir or be split into multiple reservoirs. In a type of model called a box model, a reservoir is represented by a box with inputs and outputs.

Geochemical models generally involve feedback. In the simplest case of a linear cycle, either the input or the output from a reservoir is proportional to the concentration. For example, salt is removed from the ocean by formation of evaporites, and given a constant rate of evaporation in evaporite basins, the rate of removal of salt should be proportional to its concentration. For a given component $C$, if the input to a reservoir is a constant $a$ and the output is $kC$ for some constant $k$, then the mass balance equation is

This expresses the fact that any change in mass must be balanced by changes in the input or output. On a time scale of $t = 1/k$, the system approaches a steady state in which $C^{steady} = a/k$. The residence time is defined as
 * $$\tau_\mathrm{res} = C^\text{steady}/I = C^\text{steady}/O,$$

where $I$ and $O$ are the input and output rates. In the above example, the steady-state input and output rates are both equal to $a$, so $τ_{res} = 1/k$.

If the input and output rates are nonlinear functions of $C$, they may still be closely balanced over time scales much greater than the residence time; otherwise, there will be large fluctuations in $C$. In that case, the system is always close to a steady-state and the lowest order expansion of the mass balance equation will lead to a linear equation like Equation ($$). In most systems, one or both of the input and output depend on $C$, resulting in feedback that tends to maintain the steady-state. If an external forcing perturbs the system, it will return to the steady-state on a time scale of $1/k$.

Solar System
The composition of the solar system is similar to that of many other stars, and aside from small anomalies it can be assumed to have formed from a solar nebula that had a uniform composition, and the composition of the Sun's photosphere is similar to that of the rest of the Solar System. The composition of the photosphere is determined by fitting the absorption lines in its spectrum to models of the Sun's atmosphere. By far the largest two elements by fraction of total mass are hydrogen (74.9%) and helium (23.8%), with all the remaining elements contributing just 1.3%. There is a general trend of exponential decrease in abundance with increasing atomic number, although elements with even atomic number are more common than their odd-numbered neighbors (the Oddo–Harkins rule). Compared to the overall trend, lithium, boron and beryllium are depleted and iron is anomalously enriched.

The pattern of elemental abundance is mainly due to two factors. The hydrogen, helium, and some of the lithium were formed in about 20 minutes after the Big Bang, while the rest were created in the interiors of stars.

Meteorites
Meteorites come in a variety of compositions, but chemical analysis can determine whether they were once in planetesimals that melted or differentiated. Chondrites are undifferentiated and have round mineral inclusions called chondrules. With the ages of 4.56 billion years, they date to the early solar system. A particular kind, the CI chondrite, has a composition that closely matches that of the Sun's photosphere, except for depletion of some volatiles (H, He, C, N, O) and a group of elements (Li, B, Be) that are destroyed by nucleosynthesis in the Sun. Because of the latter group, CI chondrites are considered a better match for the composition of the early Solar System. Moreover, the chemical analysis of CI chondrites is more accurate than for the photosphere, so it is generally used as the source for chemical abundance, despite their rareness (only five have been recovered on Earth).

Giant planets
The planets of the Solar System are divided into two groups: the four inner planets are the terrestrial planets (Mercury, Venus, Earth and Mars), with relatively small sizes and rocky surfaces. The four outer planets are the giant planets, which are dominated by hydrogen and helium and have lower mean densities. These can be further subdivided into the gas giants (Jupiter and Saturn) and the ice giants (Uranus and Neptune) that have large icy cores.

Most of our direct information on the composition of the giant planets is from spectroscopy. Since the 1930s, Jupiter was known to contain hydrogen, methane and ammonium. In the 1960s, interferometry greatly increased the resolution and sensitivity of spectral analysis, allowing the identification of a much greater collection of molecules including ethane, acetylene, water and carbon monoxide. However, Earth-based spectroscopy becomes increasingly difficult with more remote planets, since the reflected light of the Sun is much dimmer; and spectroscopic analysis of light from the planets can only be used to detect vibrations of molecules, which are in the infrared frequency range. This constrains the abundances of the elements H, C and N. Two other elements are detected: phosphorus in the gas phosphine (PH3) and germanium in germane (GeH4).

The helium atom has vibrations in the ultraviolet range, which is strongly absorbed by the atmospheres of the outer planets and Earth. Thus, despite its abundance, helium was only detected once spacecraft were sent to the outer planets, and then only indirectly through collision-induced absorption in hydrogen molecules. Further information on Jupiter was obtained from the Galileo probe when it was sent into the atmosphere in 1995; and the final mission of the Cassini probe in 2017 was to enter the atmosphere of Saturn. In the atmosphere of Jupiter, He was found to be depleted by a factor of 2 compared to solar composition and Ne by a factor of 10, a surprising result since the other noble gases and the elements C, N and S were enhanced by factors of 2 to 4 (oxygen was also depleted but this was attributed to the unusually dry region that Galileo sampled).

Spectroscopic methods only penetrate the atmospheres of Jupiter and Saturn to depths where the pressure is about equal to 1 bar, approximately Earth's atmospheric pressure at sea level. The Galileo probe penetrated to 22 bars. This is a small fraction of the planet, which is expected to reach pressures of over 40 Mbar. To constrain the composition in the interior, thermodynamic models are constructed using the information on temperature from infrared emission spectra and equations of state for the likely compositions. High-pressure experiments predict that hydrogen will be a metallic liquid in the interior of Jupiter and Saturn, while in Uranus and Neptune it remains in the molecular state. Estimates also depend on models for the formation of the planets. Condensation of the presolar nebula would result in a gaseous planet with the same composition as the Sun, but the planets could also have formed when a solid core captured nebular gas.

In current models, the four giant planets have cores of rock and ice that are roughly the same size, but the proportion of hydrogen and helium decreases from about 300 Earth masses in Jupiter to 75 in Saturn and just a few in Uranus and Neptune. Thus, while the gas giants are primarily composed of hydrogen and helium, the ice giants are primarily composed of heavier elements (O, C, N, S), primarily in the form of water, methane, and ammonia. The surfaces are cold enough for molecular hydrogen to be liquid, so much of each planet is likely a hydrogen ocean overlaying one of heavier compounds. Outside the core, Jupiter has a mantle of liquid metallic hydrogen and an atmosphere of molecular hydrogen and helium. Metallic hydrogen does not mix well with helium, and in Saturn, it may form a separate layer below the metallic hydrogen.

Terrestrial planets
Terrestrial planets are believed to have come from the same nebular material as the giant planets, but they have lost most of the lighter elements and have different histories. Planets closer to the Sun might be expected to have a higher fraction of refractory elements, but if their later stages of formation involved collisions of large objects with orbits that sampled different parts of the Solar System, there could be little systematic dependence on position.

Direct information on Mars, Venus and Mercury largely comes from spacecraft missions. Using gamma-ray spectrometers, the composition of the crust of Mars has been measured by the Mars Odyssey orbiter, the crust of Venus by some of the Venera missions to Venus, and the crust of Mercury by the MESSENGER spacecraft. Additional information on Mars comes from meteorites that have landed on Earth (the Shergottites, Nakhlites, and Chassignites, collectively known as SNC meteorites). Abundances are also constrained by the masses of the planets, while the internal distribution of elements is constrained by their moments of inertia.

The planets condensed from the solar nebula, and much of the details of their composition are determined by fractionation as they cooled. The phases that condense fall into five groups. First to condense are materials rich in refractory elements such as Ca and Al. These are followed by nickel and iron, then magnesium silicates. Below about 700 kelvins (700 K), FeS and volatile-rich metals and silicates form a fourth group, and in the fifth group FeO enter the magnesium silicates. The compositions of the planets and the Moon are chondritic, meaning that within each group the ratios between elements are the same as in carbonaceous chondrites.

The estimates of planetary compositions depend on the model used. In the equilibrium condensation model, each planet was formed from a feeding zone in which the compositions of solids were determined by the temperature in that zone. Thus, Mercury formed at 1400 K, where iron remained in a pure metallic form and there was little magnesium or silicon in solid form; Venus at 900 K, so all the magnesium and silicon condensed; Earth at 600 K, so it contains FeS and silicates; and Mars at 450 K, so FeO was incorporated into magnesium silicates. The greatest problem with this theory is that volatiles would not condense, so the planets would have no atmospheres and Earth no atmosphere.

In chondritic mixing models, the compositions of chondrites are used to estimate planetary compositions. For example, one model mixes two components, one with the composition of C1 chondrites and one with just the refractory components of C1 chondrites. In another model, the abundances of the five fractionation groups are estimated using an index element for each group. For the most refractory group, uranium is used; iron for the second; the ratios of potassium and thallium to uranium for the next two; and the molar ratio FeO/(FeO+MgO) for the last. Using thermal and seismic models along with heat flow and density, Fe can be constrained to within 10 percent on Earth, Venus, and Mercury. U can be constrained within about 30% on Earth, but its abundance on other planets is based on "educated guesses". One difficulty with this model is that there may be significant errors in its prediction of volatile abundances because some volatiles are only partially condensed.

Earth's crust
The more common rock constituents are nearly all oxides; chlorides, sulfides and fluorides are the only important exceptions to this and their total amount in any rock is usually much less than 1%. By 1911, F. W. Clarke had calculated that a little more than 47% of the Earth's crust consists of oxygen. It occurs principally in combination as oxides, of which the chief are silica, alumina, iron oxides, and various carbonates (calcium carbonate, magnesium carbonate, sodium carbonate, and potassium carbonate). The silica functions principally as an acid, forming silicates, and all the commonest minerals of igneous rocks are of this nature. From a computation based on 1672 analyses of numerous kinds of rocks Clarke arrived at the following as the average percentage composition of the Earth's crust: SiO2=59.71, Al2O3=15.41, Fe2O3=2.63, FeO=3.52, MgO=4.36, CaO=4.90, Na2O=3.55, K2O=2.80, H2O=1.52, TiO2=0.60, P2O5=0.22, (total 99.22%). All the other constituents occur only in very small quantities, usually much less than 1%.

These oxides combine in a haphazard way. For example, potash (potassium carbonate) and soda (sodium carbonate) combine to produce feldspars. In some cases, they may take other forms, such as nepheline, leucite, and muscovite, but in the great majority of instances they are found as feldspar. Phosphoric acid with lime (calcium carbonate) forms apatite. Titanium dioxide with ferrous oxide gives rise to ilmenite. Part of the lime forms lime feldspar. Magnesium carbonate and iron oxides with silica crystallize as olivine or enstatite, or with alumina and lime form the complex ferromagnesian silicates of which the pyroxenes, amphiboles, and biotites are the chief. Any excess of silica above what is required to neutralize the bases will separate out as quartz; excess of alumina crystallizes as corundum. These must be regarded only as general tendencies. It is possible, by rock analysis, to say approximately what minerals the rock contains, but there are numerous exceptions to any rule.

Mineral constitution
Except in acid or siliceous igneous rocks containing greater than 66% of silica, known as felsic rocks, quartz is not abundant in igneous rocks. In basic rocks (containing 20% of silica or less) it is rare for them to contain as much silicon, these are referred to as mafic rocks. If magnesium and iron are above average while silica is low, olivine may be expected; where silica is present in greater quantity over ferromagnesian minerals, such as augite, hornblende, enstatite or biotite, occur rather than olivine. Unless potash is high and silica relatively low, leucite will not be present, for leucite does not occur with free quartz. Nepheline, likewise, is usually found in rocks with much soda and comparatively little silica. With high alkalis, soda-bearing pyroxenes and amphiboles may be present. The lower the percentage of silica and alkali's, the greater is the prevalence of plagioclase feldspar as contracted with soda or potash feldspar.

Earth's crust is composed of 90% silicate minerals and their abundance in the Earth is as follows: plagioclase feldspar (39%), alkali feldspar (12%), quartz (12%), pyroxene (11%), amphiboles (5%), micas (5%), clay minerals (5%); the remaining silicate minerals make up another 3% of Earth's crust. Only 8% of the Earth is composed of non-silicate minerals such as carbonates, oxides, and sulfides.

The other determining factor, namely the physical conditions attending consolidation, plays, on the whole, a smaller part, yet is by no means negligible. Certain minerals are practically confined to deep-seated intrusive rocks, e.g., microcline, muscovite, diallage. Leucite is very rare in plutonic masses; many minerals have special peculiarities in microscopic character according to whether they crystallized in-depth or near the surface, e.g., hypersthene, orthoclase, quartz. There are some curious instances of rocks having the same chemical composition, but consisting of entirely different minerals, e.g., the hornblendite of Gran, in Norway, which contains only hornblende, has the same composition as some of the camptonites of the same locality that contain feldspar and hornblende of a different variety. In this connection, we may repeat what has been said above about the corrosion of porphyritic minerals in igneous rocks. In rhyolites and trachytes, early crystals of hornblende and biotite may be found in great numbers partially converted into augite and magnetite. Hornblende and biotite were stable under the pressures and other conditions below the surface, but unstable at higher levels. In the ground-mass of these rocks, augite is almost universally present. But the plutonic representatives of the same magma, granite, and syenite contain biotite and hornblende far more commonly than augite.

Felsic, intermediate and mafic igneous rocks
Those rocks that contain the most silica, and on crystallizing yield free quartz, form a group generally designated the "felsic" rocks. Those again that contain the least silica and most magnesia and iron, so that quartz is absent while olivine is usually abundant, form the "mafic" group. The "intermediate" rocks include those characterized by the general absence of both quartz and olivine. An important subdivision of these contains a very high percentage of alkalis, especially soda, and consequently has minerals such as nepheline and leucite not common in other rocks. It is often separated from the others as the "alkali" or "soda" rocks, and there is a corresponding series of mafic rocks. Lastly, a small sub-group rich in olivine and without feldspar has been called the "ultramafic" rocks. They have very low percentages of silica but much iron and magnesia.

Except these last, practically all rocks contain felspars or feldspathoid minerals. In the acid rocks, the common feldspars are orthoclase, perthite, microcline, and oligoclase—all having much silica and alkalis. In the mafic rocks labradorite, anorthite, and bytownite prevail, being rich in lime and poor in silica, potash, and soda. Augite is the most common ferromagnesian in mafic rocks, but biotite and hornblende are on the whole more frequent in felsic rocks.

Rocks that contain leucite or nepheline, either partly or wholly replacing felspar, are not included in this table. They are essentially of intermediate or of mafic character. We might in consequence regard them as varieties of syenite, diorite, gabbro, etc., in which feldspathoid minerals occur, and indeed there are many transitions between syenites of ordinary type and nepheline — or leucite — syenite, and between gabbro or dolerite and theralite or essexite. But, as many minerals develop in these "alkali" rocks that are uncommon elsewhere, it is convenient in a purely formal classification like that outlined here to treat the whole assemblage as a distinct series.

This classification is based essentially on the mineralogical constitution of the igneous rocks. Any chemical distinctions between the different groups, though implied, are relegated to a subordinate position. It is admittedly artificial, but it has grown up with the growth of the science and is still adopted as the basis on which more minute subdivisions are erected. The subdivisions are by no means of equal value. The syenites, for example, and the peridotites, are far less important than the granites, diorites, and gabbros. Moreover, the effusive andesites do not always correspond to the plutonic diorites but partly also to the gabbros. As the different kinds of rock, regarded as aggregates of minerals, pass gradually into one another, transitional types are very common and are often so important as to receive special names. The quartz-syenites and nordmarkites may be interposed between granite and syenite, the tonalites and adamellites between granite and diorite, the monzonites between syenite and diorite, norites and hyperites between diorite and gabbro, and so on.

Trace metals in the ocean
Trace metals readily form complexes with major ions in the ocean, including hydroxide, carbonate, and chloride and their chemical speciation changes depending on whether the environment is oxidized or reduced. Benjamin (2002) defines complexes of metals with more than one type of ligand, other than water, as mixed-ligand-complexes. In some cases, a ligand contains more than one donor atom, forming very strong complexes, also called chelates (the ligand is the chelator). One of the most common chelators is EDTA (ethylenediaminetetraacetic acid), which can replace six molecules of water and form strong bonds with metals that have a plus two charge. With stronger complexation, lower activity of the free metal ion is observed. One consequence of the lower reactivity of complexed metals compared to the same concentration of free metal is that the chelation tends to stabilize metals in the aqueous solution instead of in solids. Concentrations of the trace metals cadmium, copper, molybdenum, manganese, rhenium, uranium and vanadium in sediments record the redox history of the oceans. Within aquatic environments, cadmium(II) can either be in the form CdCl+(aq) in oxic waters or CdS(s) in a reduced environment. Thus, higher concentrations of Cd in marine sediments may indicate low redox potential conditions in the past. For copper(II), a prevalent form is CuCl+(aq) within oxic environments and CuS(s) and Cu2S within reduced environments. The reduced seawater environment leads to two possible oxidation states of copper, Cu(I) and Cu(II). Molybdenum is present as the Mo(VI) oxidation state as MoO42−(aq) in oxic environments. Mo(V) and Mo(IV) are present in reduced environments in the forms MoO2+(aq) and MoS2(s). Rhenium is present as the Re(VII) oxidation state as ReO4− within oxic conditions, but is reduced to Re(IV) which may form ReO2 or ReS2. Uranium is in oxidation state VI in UO2(CO3)34−(aq) and is found in the reduced form UO2(s). Vanadium is in several forms in oxidation state V(V); HVO42− and H2VO4−. Its reduced forms can include VO2+, VO(OH)3−, and V(OH)3. These relative dominance of these species depends on pH.

In the water column of the ocean or deep lakes, vertical profiles of dissolved trace metals are characterized as following conservative–type, nutrient–type, or scavenged–type distributions. Across these three distributions, trace metals have different residence times and are used to varying extents by planktonic microorganisms. Trace metals with conservative-type distributions have high concentrations relative to their biological use. One example of a trace metal with a conservative-type distribution is molybdenum. It has a residence time within the oceans of around 8 x 105 years and is generally present as the molybdate anion (MoO42−). Molybdenum interacts weakly with particles and displays an almost uniform vertical profile in the ocean. Relative to the abundance of molybdenum in the ocean, the amount required as a metal cofactor for enzymes in marine phytoplankton is negligible.

Trace metals with nutrient-type distributions are strongly associated with the internal cycles of particulate organic matter, especially the assimilation by plankton. The lowest dissolved concentrations of these metals are at the surface of the ocean, where they are assimilated by plankton. As dissolution and decomposition occur at greater depths, concentrations of these trace metals increase. Residence times of these metals, such as zinc, are several thousand to one hundred thousand years. Finally, an example of a scavenged-type trace metal is aluminium, which has strong interactions with particles as well as a short residence time in the ocean. The residence times of scavenged-type trace metals are around 100 to 1000 years. The concentrations of these metals are highest around bottom sediments, hydrothermal vents, and rivers. For aluminium, atmospheric dust provides the greatest source of external inputs into the ocean.

Iron and copper show hybrid distributions in the ocean. They are influenced by recycling and intense scavenging. Iron is a limiting nutrient in vast areas of the oceans and is found in high abundance along with manganese near hydrothermal vents. Here, many iron precipitates are found, mostly in the forms of iron sulfides and oxidized iron oxyhydroxide compounds. Concentrations of iron near hydrothermal vents can be up to one million times the concentrations found in the open ocean.

Using electrochemical techniques, it is possible to show that bioactive trace metals (zinc, cobalt, cadmium, iron, and copper) are bound by organic ligands in surface seawater. These ligand complexes serve to lower the bioavailability of trace metals within the ocean. For example, copper, which may be toxic to open ocean phytoplankton and bacteria, can form organic complexes. The formation of these complexes reduces the concentrations of bioavailable inorganic complexes of copper that could be toxic to sea life at high concentrations. Unlike copper, zinc toxicity in marine phytoplankton is low and there is no advantage to increasing the organic binding of Zn2+. In high-nutrient, low-chlorophyll regions, iron is the limiting nutrient, with the dominant species being strong organic complexes of Fe(III).

title: Geochemistry


text:
Talk:Context-free grammar

Derivations and syntax trees

 * The article presents this example:

For example, if we take the following grammar:
 * (1) S → S + S
 * (2) S → 1

and the string "1 + 1 + 1" then the left derivation of this string is the list [ (1), (1), (2), (2), (2) ]. Analogously the rightmost derivation is defined as the list that we get if we always replace the rightmost nonterminal first. In this case this would be the list [ (1), (2), (1), (2), (2)].

 * However, we could just as easily replace the rightmost S with S+S for the rightmost case, or we could replace the leftmost S with 1 for the leftmost case. In other words, this section should be rewritten with a better (less ambiguous) example  RaulMiller 02:32, 21 Sep 2005 (UTC)

 * The "1 + 1 + 1"-example is really hard to understand. There is (if I understood it correct) two ways to do rightmost derivation, and two ways to do leftmost derivation. In adittion the method that gives [ (1), (2), (1), (2), (2) ] actually applies to both leftmost- and rightmost derivation? Things would probably be better explained to the reader if another example is used. [Guest user], 3 Dec 2005

It is necessary to add, that arrows outgoing from node are ordered. AlexShkotin 05:14, 6 September 2006 (UTC)

 * The current example is:
 * (1) S → S + S
 * (2) S → 1
 * (3) S → a

and the string '1 + 1 + a'. Still the parsing process is not determined (neither righmost nor leftmost derivation) because there always is a choice between first expanding (via rule (1)) or terminating (via rules (2) or (3)). Although leftmost and rightmost derivation is clearly distinguished by the order of application of rules (2) and (3), this is not clear from the text. I am not sure whether an altogether different example is useful or if it is sufficient to mention point out that there are different derivation path for each type of derivation. --Larsipulami (talk) 15:20, 10 December 2009 (UTC)

 * I have significantly expanded Example 3. Does that text provide adequate explanation, or is there still something amiss?  The idea is to introduce leftmost derivations in the next example. Rp (talk) 18:52, 10 December 2009 (UTC)

 * This section is still ambiguous. As far as I can tell, there is no explanation given as to why the first rule is used first for the left most derivation. From a readers perspective, you could just as easily apply the second or third rule and terminate the parsing. - 80.176.156.118 (talk) 14:03, 29 March 2011 (UTC)

 * There's nothing wrong with that, except that you'd be deriving a different string! I have expanded the explanation even further to clarify, but I feel the amount of detail on parse trees and derivations has gone far beyond what an encyclopedia article on cfgs should provide, and there is quite a lot of redundancy now. Rp (talk) 15:22, 30 March 2011 (UTC)

 * The section claims to be validating a specific string, not creating a different one, so creating an incorrect one seems more like a mistake due to the ambiguity than a choice. This problem is gone now, more from a removal of any such explanation than clarity. - 80.176.156.118 (talk) 13:06, 31 March 2011 (UTC)

 * Yes, I rewrote some things; if this still isn't clear enough, of course your remark can be added, or the context can be removed entirely by not starting with a specific string. What do you prefer? Rp (talk) 18:31, 31 March 2011 (UTC)

 * Hi, I modified one of the leftmost derivation examples (it was using production rule 1 before the first use of production rule 2). I also altered the corresponding syntax tree, but it is now the same as the rightmost derivation tree, not sure if I have done it correctly, I am new to this. Check my work please — Preceding unsigned comment added by 2.120.159.191 (talk) 16:48, 7 July 2011 (UTC).
 * I'm not sure what you did, as I'm also not a frequent editor and can't be arsed finding your edit, but it seems to me you might have undone whatever these guys were fixing. It's still not good, I came here precisely because of that, and I've seen the same bad explanation in other websites. Saying something like "in a leftmost derivation, we expand the leftmost variable first" is not a good explanation, it is meaningless unless "first" has an effect on which production rule you pick.
 * Its meaninglessness is clear when you think of parse trees. If you have a bag of Christmas tree balls, it makes no sense to talk about a "rightmost Christmas tree" because you placed the balls on the rightmost branches first, unless you are forced to first place all the red balls, and then the blue ones when you run out, for example. Nuno pereira69 (talk) 21:45, 12 May 2022 (UTC)
 * It doesn't make much sense to reply to an 11 years old post, or to try to find out what edit it referred to at that time, and what (if anything) of it survived in the current version. If you can express your problem with the current text, I'd like to fix it in cooperation with you. Imo, your christmas-tree example misses the point. "Parsing" means searching for a derivation tree such that its projection to strings matches the input string. Different tree structures may result in the same string, e.g.

+                             +     / \                            / \    +   a                          1   + / \                               / \  1   1                              1   a                 and                                        both project to  1 + 1+a                          1+1 + a
 * The left tree is obtained by a leftmost derivation, the right tree is not. In contrast, your christmas tree example already starts from a given tree structure (rather than from a given string). Jochen Burghardt (talk) 08:35, 13 May 2022 (UTC)

Decidability

 * It is not possible to construct a general algorithm which takes as input two context-free grammars and decides whether the two grammars generate the same language; nor is it decidable whether their languages have a single string in common. It is however possible to decide whether a given context-free grammar generates a non-empty language or not, and it is also possible to decide algorithmically whether a given context-free grammar generates an infinite language or not.

Is it possible to decide whether given context-free grammar is equivalent to given regular grammar ? In particular is it possible to decide whethere there is single string that doesn't belong to context-free language (that is, whether or not is it equivalent to .*) ? Taw 14:41 Apr 6, 2003 (UTC)
 * The answer for your first question is Pumping lemma. -- Sundar 05:08, Feb 15, 2005 (UTC)
 * And the answer to your second question is yes. See Rice's Theorem. -- JBolla
 * It seems both answers are wrong. It is undecidable whether a given context-free grammar generates all words over its alphabet. Jochgem 23:45, 11 March 2007 (UTC)
 * The first answer is indeed wrong as well: it is undecidable whether any given context-free language is regular (I was surprised to learn this, too. Google for references).  The pumping lemma isn't good enough: some non-regular languages can be pumped. Rp (talk) 23:29, 11 April 2008 (UTC)
 * I have tried to search for results about "whether any given CFL is regular" without success; the terms I have come up with appear together too often in other contexts. Can you reproduce the search that led to your earlier discovery? 128.105.181.52 (talk) 19:41, 2 February 2012 (UTC)
 * I added a source, found by searching for the terms "context-free", "is regular", and "undecidable" in Google books. —David Eppstein (talk) 20:10, 2 February 2012 (UTC)

On the page Context-free_language is is stated:

 * Intersection Emptiness: Given two context-free grammars A and B, is $$L(A) \cap L(B) = \emptyset $$ ? However, the intersection of a context-free language and a regular language is context-free, and the variant of the problem where B is a regular grammar is decidable.
 * Containment: Given a context-free grammar A, is $$L(A) \subseteq L(B)$$ ? Again, the variant of the problem where B is a regular grammar is decidable.

And judging from Regular_grammar and Regular_language it seems that regular languages can easily be described by context-free grammars (which is natural, as any regular language is also context-free), so a right-linear CFG or a left-linear CFG generates a regular language. So there are *some* CFGs for which regularity is decidable, right? I am not questioning the theory, I just think it maybe could be explained more clearly? --Lasse Hillerøe Petersen (talk) 20:21, 7 December 2014 (UTC)
 * What's unclear? The general problem is hard. Some special cases of it are not hard. That seems to be what we say. —David Eppstein (talk) 21:21, 7 December 2014 (UTC)
 * My guess: the sloppy way such problems are traditionally formulated. The theorem as usually stated: it is undecidable whether a context-free language is regular. This is a very sloppy formulation: it doesn't state how we know that the language in question is context-free. Properly stated, the theorem says: it is undecidable whether, given an arbitrary context-free grammar (or, equivalently, an arbitrary pushdown automaton), the language it generates (or recognizes) is regular. In other words: whether some left-linear or right-linear grammar describes the exact same language.  Strictly speaking, this is a stronger theorem. Now, it is immediately clear that if the given CFG happens to be left-linear or right-regular already, the affirmative answer follows immediately.  All the more surprising that it there are so many other ways to describe regular languages with CFGs that it is impossible to devise an algorithm that decides for any given CFG whether it describes a regular language. Rp (talk) 23:20, 7 December 2014 (UTC)

Syntax or semantics
Context-free grammars are important because they are powerful enough to describe the syntax of programming languages

(Well...context-free grammars can describe most of the syntax of programming languages. For example, any programming language that requires that variables be declared before use is not fully describable via a context-free grammar, essentially because there can be arbitrary amounts of source code between declaration and use--see the reference to the "pumping lemma" below. Such constraints are typically swept over into the corner, labelled "semantics," and dealt with outside of the parser mechanism proper. In the example, "semantic action" code is attached to the grammar rule that recognizes identifiers to check against a symbol table.) --24.36.158.101

 * Right, the requirement to declare before use is called "semantics" rather than "syntax", so the sentence in the article is correct: the syntax of programming languages is describable by context-free grammars. --LC

 * Not exactly - it's debatable whether "declare-before-use" is really "syntax" or "semantics". In C and C++, for example, it's impossible to check whether a source file is syntactically correct without building a symbol table while parsing that can at least distinguish between typedef'd and "regular" identifiers.  The syntax of C and C++ critically depends on the distinction betwen those two forms of identifiers, which depends on what you're calling semantic information.  In addition, there's plenty of other such stuff in various languages that's usually "swept into the corner" but is unquestionably syntax.  For example: the ad hoc precedence rules built into parser generators to resolve dangling else and similar conflicts; the whole "longest match" convention that is built into lexical analyzers; the layout mechanisms of many more recent languages such as ML, Haskell, and Python.  Then there's the fact that the C++ grammar has ambiguities that cannot be resolved by any finite amount of lookahead, and so the C++ standard simply states ad hoc disambiguation rules which implementors have to follow by making the parser capable of looking ahead an arbitrary distance in certain situations.  As far as I can tell, practical languages that really follow a "pure" context-free syntactic paradigm are rather few and far between.  Brynosaurus 15:00, 13 Aug 2004 (UTC)

 * It's my understanding that because of these facts C, C++, and the other languages do not have context-free grammars. A context-free grammar is an ideal for a computer programming language which is seldom achieved - basically because many things which are very useful for programming languages are not possible in a context-free grammar.
 * This is the strict sense of "context-free" grammar. When programmers think about "grammar", "syntax", and "semantics" they usually have much looser usage of these terms. — Hippietrail 02:13, 14 Aug 2004 (UTC)

 * Quite so. It is certainly almost universal practice to use BNF notation informally as a method of concisely describing or suggesting the general, overall structure of a language's syntax.  But it is almost never the case that these BNF notations actually formally specify the syntax of the language by themselves.  Brynosaurus 06:18, 14 Aug 2004 (UTC)

 * I have added some words in the article in the hope of clearing up the confusion. It is a fact that the equivocation of 'syntax' and 'context-free grammar' is common in computer science.

Phrase structure grammars
Phrase structure grammar and context-free grammars

There is a redirect from Phrase structure grammar to this page.

Does this mean that Phrase structure grammars are just context-free grammars in any case? Isn't there more to say about Phrase structure grammars?

 * PSG isn't a precise term. CFGs are definitely PSGs, but there are also CSGs (context-sensitive grammars), for example, which could also be described as PSGs. The redirect seems sensible enough to me for the moment, since it's hard to imagine that an article on PSGs could be written which didn't just duplicate material in Context-free grammar and Chomsky hierarchy. I agree though, that the redirect is misleading. Perhaps it would be better to have a stub with links to Context-free grammar and Chomsky hierarchy? Cadr 23:11, 14 Feb 2005 (UTC)

It ought to be a stub if they are not equivalent.Otherwise it is misleading. -- Sundar 05:08, Feb 15, 2005 (UTC)

 * I agree with Sundar. –jonsafari 22:38, 18 June 2007 (UTC)

I did some more looking around on this. Here's the score from the most reputable sources I could find:
 * Chomsky Three models for the description of language (1956) introduces the term "phrase structure grammar". Here he is clearly referring to a CFG.
 * Nope, what he defines is in Wikipedia under formal grammar (I always hated the name of that article). Rp (talk) 15:10, 28 September 2009 (UTC)

 * Jurafsky and Martin's Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition (2000) says PSG is a synonym for CFG.
 * They're wrong.

 * JE Hopcroft and JD Ullman, Introduction to Automata Theory, Languages, and Computation (1979) might in some sense be more reputable than Jurafsky and Martin, and says PSG refers to anything in the Chomsky hierarchy. This might reflect a change in usage between the introduction of the term and this work's publication.
 * It doesn't - they use Chomsky's definition. Rp (talk) 15:11, 28 September 2009 (UTC)

 * Lewis and Papadimitriou Elements of the Theory of Computation (1998) doesn't address the issue.

So this seems like a disputed usage. At any rate, no one uses the term in any current work. The stub idea seems reasonable. kraemer 00:39, 20 June 2007 (UTC)

 * I changed it to a stub. Cadr 18:21, 21 June 2007 (UTC)

 * As far as I can tell: computer science doesn't use the term phrase structure grammar at all, while it is the standard term in (generative) linguistics. Hence the confusion. Rp (talk) 23:32, 11 April 2008 (UTC)

Natural languages
It would be nice to include some statement about whether natural languages are context-free in this article. On this topic, the article Bambara language has the following note:

 * In mathematical linguistics Bambara is regarded with interest, since for only very few languages it was possible to show that they were not context-free. For Zurich German and Dutch the proof is based on sentence construction, whereas the proof for Bambara is based on word construction.

I wonder what is statement is really supposed to say, because I find it a bit difficult to believe. Can it really be so hard to find an example showing that English is not context-free? --Saforrest 12:37, Apr 19, 2005 (UTC)

BNF and Production rules
The article states that "BNF (Backus-Naur Form) is the most common notation used to express context-free grammars.", but still the article make use of production rules like V→w instead of V::=w, is that because production rules and BNF are interchangeable ? --Robsy 11:32, 2 May 2006 (UTC)

 * No, it is because theoretical articles about context-free grammars use the arrow, while the BNF notation is pretty much restricted to manuals or textbooks that describe the syntax of a concrete language. The reason for the difference, by the way, is that BNF was designed for ASCII-only text. Rp 09:28, 25 July 2007 (UTC)

Lojban
I doubt that Lojban is actually context-free. It probably were context-free if none of the terminator cmavo were elidable. Icek 22:53, 28 June 2006 (UTC)

 * It is parsable at the word-level with an LALR parser (there is at least one implementation of a parser done using Yacc). However, should it really be listed on the context free grammar page (I'd argue not)?  Saying it has "an immense expressive power" is definitely POV and there is no citation, so I'm removing that part.  JordanDeLong 03:34, 24 August 2006 (UTC)

 * AFAIK it is not possible without some preprocessing. From the Lojban Reference Grammar: Lojban is not in itself LALR1. There are words whose grammatical function is determined by following tokens. As a result, parsing of the YACC grammar must take place in two steps. [...].

 * The problem that I see with the alleged context-freeness of Lojban is as follows: Consider a Lojban sumti (an argument to a predicate) which contains subordinate clauses which contain the words be (marks the beginning of the relative clause) and be'o (which ends a relative clause). The subordinate clause may itself contain subordinate clauses and so on. However deeply nested the subordinate clauses are, all the be'o terminators may be elided if there is a single ku terminator terminating the sumti (and if there are no ambiguities stemming from multiple subordinate clauses on the same level, for further details see, section 7). Icek 20:15, 25 August 2006 (UTC)

 * Got ya: I think you're right.  I went ahead and removed it from the page.  It may need some other items in "Other Examples" now, though.  JordanDeLong 02:55, 26 August 2006 (UTC)

How useful is this page?
You either understand all this jargon, in which case you already know what a "context free grammar" is...or you don't, and this is Greek to you.

Useless.

''The comment above is useless. I found the explanation on this page clear and helpful.'' --Whisk3rs 00:07, 17 May 2007 (UTC)

 * I strongly disagree. An encyclopedic article is supposed to be understandable for the interested layman.  This article in its present state is not; it presupposes familiarity with the basic notions of formal language theory.  The article would greatly benefit from clear examples, and external references to more introductory material. Rp 09:32, 25 July 2007 (UTC)

 * As someone who has studied this topic in depth, it's hard for me to get perspective on just what is hard for the layman to understand. Do we have a layman that is willing to make specific criticisms that I can address?  --Doradus 06:15, 27 July 2007 (UTC)

 * I too have just visited the page and after a couple of readings found it quite confusing, clearly written by and for people who already understand. To Address Doradus's request...
 * "In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form
 * V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (possibly empty)."  In this sentence every key word is linked, so readers coming here must immediately leave and try to understand other pages before they can even understand the introduction.  I fully understand that prior information is required to understand some topics, but I think the intro should make some attempt to explain itself in simpler terms that are understandable in themselves.
 * "The term "context-free" expresses the fact that nonterminals can be rewritten without regard to the context in which they occur." This is a most confusing sentence!  What does 'rewritten' mean?  What 'context'?  Are we talking about letters?  Words?  Clauses?
 * "A formal language is context-free if some context-free grammar generates it." Again, I don't know what this is trying to say.  I instinctively want to put this sentence in the passave (eg. '...if it is generated according to a context-free grammar').  It just seems like a tautology.
 * "These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton." Is 'exactly' needed here?  'Recognized'?  How can an automata recognize anything?  This seems to be a misuse of wording.  The correlate on the pushdown automata page is better... "Pushdown automata are equivalent to context-free grammars: for every context-free grammar, there exists a pushdown automaton such that the language generated by the grammar is identical with the language generated by the automaton, which is easy to prove.".

 * This was just the introduction, but I feel this is the weakest part of the page. It would be great if someone with a clear understanding of the topic could make this more accessible (I don't mean this as a criticism of the original writers though - there are many scientific pages on wiki that start out like scientific papers and need to be clarified for the average reader.)  --218.143.30.7 (talk) 01:20, 10 December 2008 (UTC)

 * The basic problem is that a context-free grammar is just a particular type of grammar so we don't want to repeat all the things that really belong in an explanation of what a grammar is, yet people clearly expect to be able to read this article without reading the article on (formal) grammar first. How to resolve this, I don't know. Rp (talk) 22:11, 21 February 2009 (UTC)
 * I don't think we can solve this, you really do need to know the basics of formal language theory or automata theory in order to understand this content properly, especially because it is so abstract. We should not remove important information simply because it confuses some people.  It would be better just to introduce the material in a more intuitive manner, and then move onto formal definitions. Ben1220 (talk) 07:31, 30 November 2009 (UTC)

 * I kinda agree. The only real point of this concept is that a context-free grammar is one that can be put on a linear tape, symbol by symbol without losing any meaning.  The purpose of such is really for loading the tape for a Turing Machine.  Average64 (talk) 20:41, 26 October 2013 (UTC)

I tried to add a simpler explanation that most people could understand to the introduction just now. — Preceding unsigned comment added by Programmers are evil (talk • contribs) 20:24, 27 October 2015 (UTC)

 * I am a computer scientist - the first part of this page is very off-putting because it jumps straight into the formal definition. It looks like it has been written by someone who does not have a clue what this subject is all about (not that i am necessarily suggesting that is the case). If they did then they would write something that can be understood by a human being. This page needs to be rewritten in such a way that a newcomer to the subject can see immediately what it means without seeing some formal (and potentially cryptic looking) mathematical statement. The formal definition should at the very least come a sentence or 2 after the basic/ friendly description. I am looking into a way of rewriting it somewhat but people may consider it overly complex - which may make it even worse or confusing.81.103.229.191 (talk) 23:37, 16 March 2016 (UTC)

 * I have just rewritten the first bit to try to make this page actually usefull. I presume the so called experts will tear me to shreds for it ;). However, I'll note that the origional version clearly didn't make sense to anyone because it contained some obvious BS... Tim.thelion (talk) 20:14, 3 June 2016 (UTC)

I agree that an informal motivation would be a good idea; I'm thinking about a natural language example along the image shown here. We could give a small excerpt of an English grammar that just generates the sentence. - Jochen Burghardt (talk) 22:20, 19 March 2016 (UTC)

A first attempt to realize my above suggestion is shown to the right. I hope the tree image might be widely familar from English school education. The image caption could explain some issues of CFGs. - Presentation problems are: the grammar takes too much horizontal space; however, when the syntactical categories are abbreviated (like "VP" for "Verb_Phrase") to save space, they'd need to be explained. commons:Category:Syntax trees in English contains 159 syntax trees, but none of them fits perfectly here; maybe we need to design a 160th one. - Jochen Burghardt (talk) 20:04, 25 March 2016 (UTC)

Clarify clarify and clarify more
A starting point would be to add an explanation of the used symbol S to the first example. It represents a grammar? In that case, would G be more appropriate? No? Why? Also, the use of the arrow symbol (product?) could be linked to an article describing that symbol etc. The use of symbols instead of human language warrants for an easy reference material to symbols used. Otherwise the use of symbols serve only an obfuscation purpose, being informative only to those already adept in the topic, which doubtfully is the purpose of Wikipedia.
 * The link is right there; click on grammar. Rp (talk) 15:15, 28 September 2009 (UTC)

AnBnCn Example and PEGs
This particular language can be generated by a parsing expression grammar, which is a relatively new formalism that is particularly well-suited to programming languages.

I've cut this from the head of the article. PEGs are relatively new, and I see no reason why they would be differentiated from any of the number of well-established formalisms that can also accept the language AnBnCn, especially since this is the canonical type 1 language (context-sensitive).

context free grammar page suggestion - request for clarity
68.122.42.35 (talk) 03:33, 25 October 2008 (UTC)

In the article "context-free grammar" the first paragraph could use a little clarity.

The following sentence: "The term "context-free" expresses the fact that nonterminals can be rewritten without regard to the context in which they occur" could really use an example or another sentence or two to describe it. I was unable to figure out what this meant, possibly not because I'm stupid. (i.e.: I'm not stupid, which may or may not be why I couldn't understand the above sentence :P )

I am not formally trained, but then, that could be seen as permissable for wikipedia.

Thanks to all you geniuses who are teaching me math and computer science.

 * I originally wrote it so I have attempted to clarify it; however, I'm meeting an obstacle. A context-free grammar, as the article states, is a particular type of grammar.  The remark is indeed not understandable if you don't know how a grammar is used (namely, by using its production rules to rewrite strings of symbols until a string is produced that contains no nonterminal symbols, and considering the total set of terminal strings that can be produced in this way from some initial symbol).  But reiterating this in this article would be redundant to anyone who has bothered to look at the grammar article.  You are assumed to follow the link to grammar if you don't know what is meant by that.  Apparently, you didn't, which suggests that many other readers won't do it, either.  If you can suggest an elegant way out of this dilemma, please let me know. Rp (talk) 22:50, 9 January 2009 (UTC)

 * Yes, Rp, it's an ugly conundrum often encountered in all kinds of technical writing. There are a number of ways I've seen used to resolve it:

 * 1) (Possibly the least effective:) Pretend there's no problem, and hope the readers are so keen to understand that they'll follow every link you give them.
 * 2) (Almost as bad:) Tell the reader that the following explanation will only make sense if one first familiarises oneself with certain prerequisites, which you then list.
 * 3) (Better than nothing:) Prominently rank the article as "Master-class" or "Genius-class" on the difficulty scale. Who knows, it may motivate the readers to try harder!
 * 4) (A workable compromise:) Write a brief introductory sentence (or paragraph) that summarises the prerequisite knowledge, perhaps informally, perhaps not. Your paragraph above comes close to doing the necessary. (Optionally also preface the introduction by saying that more advanced readers can skip the following paragraph, page or section - and try not to make the rest feel inferior or patronised! How many of my uni maths texts said: "Recall that ... {Uglich's Barking Lemma here restated in five lines of incomprehensible formalism}"!?)
 * 5) (Probably the most effective:) Provide pop-up or hover- "hint text" balloons; see for example almost any Microsoft online help documentation, which uses a dashed underline to signal that hint text is available. AFAIK, MediaWiki doesn't support such a mechanism; but maybe it should? Personally, I appreciate this approach, as it lets me brush up on forgotten detail without losing my place on the page; it's a minimal distraction to the main task at hand.
 * HTH. yoyo (talk) 19:59, 30 April 2009 (UTC)
 * I'd go for 4, obviously. Your last suggestion is great, but I'd implement it as a general Wikipedia user interface feature, i.e. for arbitrary links instead of specific links.  Like Google Maps does with its Wikipedia links. Rp (talk) 16:10, 3 June 2009 (UTC)

link proposal
I stumbled upon a tool that produces images from context free grammars. Here is the link http://www.contextfreeart.org/index.html 140.203.154.11 (talk) 18:37, 11 November 2008 (UTC) mihai andrei
 * Nice; this kind of stuff is typically associated with L-systems, which reminds me that L-systems should definitely be mentioned in the article. Please do ... Rp (talk) 22:52, 9 January 2009 (UTC)

Cycles?
Under the formal definition section, the last in Additional Section 5 says "no cycles". In this context, what exactly is a cycle? 66.69.234.193 (talk) 22:05, 24 January 2009 (UTC)

The only reasonable cycle that comes to my mind is something like this S->BA,B->S. If you have no that kind of cycles, you can generate just finite amount of products from the CFG and thus the generated language is star free. One might want to use that kind of CFG to compress text. —Preceding unsigned comment added by Hiihammuk (talk • contribs) 12:44, 25 January 2009 (UTC)

 * I have added formalizations of the criteria for properness, please verify. Rp (talk) 22:13, 21 February 2009 (UTC)

 * Think you may have a typo:
 * no cycles: \neg\exists N \in V: N \stackrel{+}{\Rightarrow} N
 * should perhaps instead read:
 * no cycles: \neg\exists N \in V: N \stackrel{*}{\Rightarrow} N
 * yoyo (talk) 19:31, 30 April 2009 (UTC)
 * It's not a typo: a zero-step derivation from N to N is not a cycle. Rp (talk) 16:06, 3 June 2009 (UTC)

Decidability again
I have read this article a few times over the months, and never noticed that it mentioned (in the Normal Form section) that the membership problem is decidable (i.e. determining whether a string is generated by a given grammar). I think this should get more prominent mention in the article. Maybe in the summary? It at least shouldn't only be buried at the end of the normal form section. --pdf23ds 24.174.103.112 (talk) 18:17, 17 May 2009 (UTC)

 * This is implied by the remarks about parsing algorithms. Incidentally, I believe the statement while the widely used LR and LL parsers are more efficient algorithms that deal only with more restrictive subsets of context-free grammars is incorrect: they aren't more efficient, only simpler. Rp (talk) 15:19, 28 September 2009 (UTC)
 * The text now reads: Deterministic grammars (...) These classes are important in parsing: they allow string recognition to proceed deterministically, e.g. without backtracking.' This is still wrong: arbitrary grammars can be parsed without backtracking, using essentially matrix multiplication, see Cocke-Younger-Kasami algorithm and Earley parser. Rp (talk) 11:42, 9 December 2009 (UTC)
 * I have rewritten these paragraphs - please review. Rp (talk) 20:09, 31 March 2011 (UTC)

Chomsky's beliefs
I like Likebox's edits a lot in general, but I'm not so happy about the references to Noam Chomsky's beliefs. The article should provide facts about cfgs, not beliefs. And while they are at the core of Chomsky's frameworks for describing syntax, they were always complemented with transformations in some form, so the reader shouldn't be left with the impression that syntax == context free grammar in Chomsky's eyes. Rp (talk) 19:32, 11 January 2010 (UTC)

 * Yes, I suppose that might belong elsewhere. The only reason I placed it there is because I think that the only observation Chomsky made that is not controversial is that context free grammars are very special types of grammars, and that context free grammars are suited to describe all of the complex grammatical clause-nesting/adjective-listing in natural language. Everything else he says is controversial, but I thought that this part is univerally accepted.Likebox (talk) 03:42, 12 January 2010 (UTC)

I've modified the section slightly, because Chomsky has never believed that language is strictly context free, but rather that it has a context free component who's output is manipulated by further decidedly non-CF mechanisms (at the time, transformations, and currently, movement). This is clear in his work, when he addresses the inadequacy of CFG for various phenomena. --Augur (talk) 08:18, 1 February 2010 (UTC)

 * Thank you-- I am sorry for not being completely accurate about this, I always mean to, but I never read enough of Chomsky's work.Likebox (talk) 17:53, 1 February 2010 (UTC)

True context free grammar vs. log-context free grammar
There is a distinction between the grammar of parentheses matching () and the grammar of matching two types of parens (([][])[]). The first language can be approximatly parsed by a finite automaton exponentially well, meaning that while it is technically context free and requires a stack, a finite automaton with a counter of n-bits can match strings of matching parens up to a depth of 2^n. Effectively, this means that a regular grammar will work to match the strings, and I wouldn't call that a real context free grammar. I would call it a "log context free grammar". I don't know what the official term is, if there is one.

On the other hand, with two types of parens, n bits can only work up to a depth of n. This is a true context free grammar, it can't be approximated well by a regular grammar, since you need to push the type onto the stack. The languages of interest, natural and computer languages, are true context free grammars.Likebox (talk) 13:55, 19 January 2010 (UTC)

 * Yes, with a finite nesting level, the stack is finite, so the language is regular. Rp (talk) 23:08, 26 February 2010 (UTC)

 * Of course that's true, but that's not what I was saying. I wanted to point out that there is a distinction between matching one type of parentheses and matching two different types of parentheses. Using a finite memory counter with n bits of memory, you can match 2^n levels of parentheses by using this stupid trick: scan the string left to right, increment the counter wheneve you see "(", decrement the counter wheneve you see ")" and make sure the counter is always positive.

 * This stupid trick doesn't work when you have two different types of parentheses. For two types of parentheses, no combination of counters will work--- you need a real stack. What this means is that parentheses matching is exponentially well approximated by a regular grammar, while two-types of parentheses are only at best linearly approximated by any regular grammar. This distinction is probably not original to me. I was hoping for a source.Likebox (talk) 23:23, 26 February 2010 (UTC)

 * A more language theoretical way of saying the same thing: if I want to make a finite automaton match parentheses up to n-levels deep, I need exactly n-states, which represent the nesting depth. If I want a finite automaton to match two types of parentheses to n-levels of depth, I need 2^n states. Every context free language has a complexity constant C, the "exponential growth number" which tells you that to match expressions of depth n you need C^n states. For one-types of parentheses, and for the most commonly cited examples of context free grammars, the constant C is 1, which is a ridiculously special case--- I think it should be classed as an intermediate stage between regular and true context free.Likebox (talk) 23:32, 26 February 2010 (UTC)

Natural human languages never allow for overlapping constructions
Never? How then does one account for such a construction (Catullus):

Sed mulier cupido quod dicit amanti in vento et rapida scribere oportet aqua

 * Transliterate it and any linguist will tell you.Likebox (talk) 23:52, 24 January 2010 (UTC)

Thank you. I just so happen to be a linguist. By "transliterate" I suppose that you meant "translate". So here:

Word for word :

But [a] woman eager what [she] tells [a] lover in [the] wind and swift [to] write one-should water

In English now:

But what a woman tells an eager lover ought to be written in the wind and in swift water. —Preceding unsigned comment added by JacquesGuy (talk • contribs) 00:12, 25 January 2010 (UTC)

 * By transliterate, I meant say what each word is, and any dangly modifiers that it has, like one that makes it act as a subject or something.

 * First off, is this poetry? Poetry allows some crazy constructions, like

 * Along the beach he said we should walk.

 * Which would not seem to normally be allowed, because "Along the beach" is attached to a clause buried a level down. I don't speak many languages, and all the languages I speak lack those dangly parts of words that tell you what part of speech they are. So perhaps there are overlapping clauses in latin.

 * Secondly, I think that you are purposefully obscuring the latin meaning. I think a better translation would be:

 * But a woman is eager that what she tells a lover in the swift wind should be written, and in the water.

"Cupido" is masculine dative, "eager" in "a woman is eager" is feminine nominative, i.e. "cupida"

Go learn Latin. End of discussion. —Preceding unsigned comment added by 61.68.162.228 (talk) 06:15, 26 January 2010 (UTC)

 * This preserves the word order and makes the non-overlapping clauses manifest. On the other hand, for all I know, Latin just might admit overlapping clauses. Please educate me if it does.Likebox (talk) 01:02, 25 January 2010 (UTC)

 * The point of the example is to explain the central role of Chomsky's "merge" operation. What this does is merge together parts of a sentence into larger objects. Merge only acts one way, so that in the sentence:

 * The man walked to the store is green

 * (The man (walked to the store) gets merged, and then "is green" doesn't have anything to merge with. There is no analogous "split" operation which would allow two-sided merge like this:

 * The man walked to the store---the store is green.

 * Where a split of the store allows it to merge with the predicate on the right and simultaneously with the rest of the stuff on the left. It is this property which makes language special, and leads it to be described by a parse tree, and not by a parse graph. But many linguists dispute Chomsky's analysis, and having seen the crazy example of Piraha, I am not certain of anything anymore.Likebox (talk) 01:13, 25 January 2010 (UTC)

 * Perhaps what we're trying to tell you is that perhaps you should be cautious about editing this article until you learn that linguistics didn't exactly start with Chomsky, nor will it end with him; and formal language theory, as used in computer science, on which he has had a great impact, is a related, but distinct discipline.  (I do appreciate your attempts to clarify certain issues.) Rp (talk)

 * Linguistics seems to be a primitive field to me, an dominated by nonmathematical people.Likebox (talk) 12:55, 27 February 2010 (UTC)

Non context-freeness of Swiss German
The article in question points out that Swiss German has a non context free construction, which involves the following:

Jan says that (we-1) (Mary-1) (the house-2) helped-1 paint-2

The numbers say which nouns go with which verb. is is not stack based, otherwise it would be:

Jan says that (we-1) (Mary-1) (the house-2) (painting-2) (helped-1)

So agreed, it's not context free. But you need to go several levels deep to make this work. The claim that they make is that you can go on in this pattern in Swiss German with more nouns and more verbs

Jan says that we-1 Mary-1 Martha-2 Sally-3 the house-4 told-1 tell-2 help-3 paint-4

If you find something like this, that would be the clincher. But I have not been able to verify this schema as grammatical in Dutch German, and the gloss provided by the authors for their analogous sentence was insufficient to determine whether it was like the above.

But the construction in question is peculiar to Swiss German, and Dutch, while Chomsky was working with English. It is manifestly obvious that English grammar is context free. I don't know how this article can be used to support the statement that "Chomsky's observations about the non-context freeness of natural language has held up", especially that I don't see any examples analogous to the above in Chomsky, and I don't know of any in English.Likebox (talk) 13:00, 9 February 2010 (UTC)
 * Chomsky has always explicitly worked on a universal theory of language, i.e. one that would not be tied to any particular natural language such as English. Rp (talk) 17:02, 22 April 2010 (UTC)

Non-context free examples
The example of an overlapping construction:

 * [John saw (a car in the ad yesterday] with green headlights)

Is not as overlapping as the Martian

 * [John walked to (the store] is green)

Which is truly inhuman. The second is a better example, I think, because the first is too natural--- it could be produced. The second shows what a truly non-context-free language would look like.

 * Wait ...
 * The point of the example was to illustrate your statement that human language is context-free, but it isn't - not completely. Examples should illustrate both the sense in which it is context-free and the fact that it isn't completely.
 * Your example doesn't illustrate that language is context-free. What makes it "inhuman" to you is the appearance of two main verbs without a conjunctive.  This is easily fixed, e.g., in Green John walked to the store or John walked to the store all green or John walked to the store and is green.  I don't see how your example is any less context-free than the other examples.
 * My example can be criticized, but for a different reason: if we regard yesterday as a postmodifier of the ad, we do obtain a context-free constituent structure.
 * I'm happy to trade my example for a better one. But I believe the way in which your passage argues for the contextfreeness of natural language is rash and introduces fuzziness into the article (see below). Rp (talk) 15:16, 21 February 2010 (UTC)

 * (It is not a good idea to break up comments like this, because it makes the discussion hard for others to follow, but I will respond in the same style).

 * You misunderstood the Martian sentence: [John walked to (the store] is green) is not saying that John is green, its saying that the store is green. The sentences "overlap" in a way that is not present in any human language. I give this example to explain that human language (and human thinking) almost automatically makes structures that do not overlap, and there is no a-priori reason for this. It's just always true that we chunk up sentences into structures in which each substructure plays a unique role. In the "martian" example, one occurence of "the store" splits to play two roles, as object and subject of two separate verbs. That never happens in human languages. It was difficult to even conceive of the example.Likebox (talk) 22:22, 21 February 2010 (UTC)
 * I wouldn't be too sure. In English, we use John walked to the green store to say that, but I can see no reason why your coinstruct would be inhuman - compare John painted the store green. Rp (talk) 23:41, 26 February 2010 (UTC)

 * The issue is that it is difficult to even conceive of language with parallel overlapping constructions, where a word plays two different roles at once, as subject of one sentence and as object of another. We want our sentences to have chunks that make grammatical objects of the same types as single words. "John painted the store green" is perfectly normal. "John green painted the store" is ungrammatical, but conceivable. "John painted the store is open green" is inhuman.Likebox (talk) 12:47, 27 February 2010 (UTC)
 * What is accusative and infinitive? 2A0A:A541:59A5:0:21BF:4D76:E67E:55E1 (talk) 04:11, 19 August 2023 (UTC)

This example of an overlapping construction is very good--- I came up with much worse examples. But it never occurs in the New York Times (I don't think), and it has a colloquial flavor (at least to my ears), precisely because the dangling "with green headlights" is not in the proper place. I feel like it's a "John saw a car with green headlights in the ad yesterday", mangled up as someone said it. But I might have been programming a computer too long.
 * Programming languages are just about as context-free as natural languages. I'm no specialist in the syntax of English and it's risky to reason from a single example.  We need examples from the linguistic literature with references. Rp (talk) 15:16, 21 February 2010 (UTC)

 * (again--- interspersing makes talk-pages unreadable--- but I will do the same)
 * The problem is that I have not found the linguistic literature to have any good examples in English. The examples everyone cites are in Swiss German. If you sort out what's going on first by discussion, it will make the literature search much easier when the time comes.Likebox (talk) 22:27, 21 February 2010 (UTC)

It would be good to have two examples--- a truly Martian language, with tons of overlapping constructions everywhere (it's easy to make one up), and an example in English like the one above. Unfortunately the one above sounds very colloquial and marginally grammatical, Do you know of a similar example in formal writing?Likebox (talk) 05:59, 21 February 2010 (UTC)

 * No, but I'll try to find something.
 * What bothers me about your introduction, and this discussion, is that it blurs the notion of context-free grammars as a technical term. In formal language theory, a language is context-free if it can be described by a context-free grammar, not if it can be described by a context-free grammar plus postprocessing on the parse tree, as is the practice in Chomskian linguistics and computer science.  By saying "language is context-free", you mean the latter, inexact sense, not the former, exact one.  This introduces a discrepancy between the introduction and the formal definitions that follow. Rp (talk) 15:16, 21 February 2010 (UTC)

 * The post-processing on the parse tree is not required for most english sentence syntax, and Chomsky does not introduces it for the purpose of describing phrase strctures. He was describing transformations, which are taking a declarative sentence and turning it into a question, stuff like that.Likebox (talk) 22:27, 21 February 2010 (UTC)

 * I know, but my point is that allowing arbitrary transformations on a parse tree makes the resulting descriptive formalism non-context-free, actually Turing-complete, from a formal language point of view. So you can't just say: well, language is context-free, but for these transformations, because you're going to have to come up with a novel justification of why context-free grammars and transformations are "the right thing to do", expressive power isn't going to cut it anymore.  Besides, while Chomsky happens to be fluent only in English, perhaps Hebrew and maybe a couple of other languages, he does claim universality for his theories, so dismissing examples in my native tongue (Dutch) or on Latin as "not English" is not the appropriate way to deal with this.  In any case, I believe such discussion doesn't really belong in this article, which should explain what a context-free grammar is, and doesn't necessarily have to answer the question whether natural language is context-free. Rp (talk) 23:41, 26 February 2010 (UTC)

 * You don't understand what I am saying: the transformations don't describe the grammar at all. They are only there for relating one sentence to another. I am saying English grammar is a straight BNF (other people said this in the 70s too).Likebox (talk) 04:11, 27 February 2010 (UTC)

 * That is not what Chomsky says, who does use transformations to describe the syntactic structure of sentences (claiming that the real sentence is a "surface structure" that arises out of a "deep structure" by transformation). Rp (talk) 17:15, 22 April 2010 (UTC)
 * Oh, and by the way, I believe the standard example in Dutch is related to chains of verbal complements, as in
 * You shouldn't want to help me wash the dishes
 * which can be expressed in Dutch as
 * Je zou me niet moeten willen helpen afwassen
 * but I must be wrong, as I don't see how the Dutch sentence structure is fundamentally different from the English one. Rp (talk) 23:55, 26 February 2010 (UTC)

 * The difference is in the order of the verbs. The english:

 * You (shouldn't want to (help (me (wash (the dishes)))))

 * has a context free form--- everything is properly nested. Or numbering stuff like a previous section (to see what goes with what verb):

 * You(1s) shouldn't want(1) to help(2) me(2s) wash(3) the dishes(3o).

 * Numbering the verbs
 * You(1s) me(1o) not-want dishes(2o) help(1) wash(2)

 * Note that unlike the english, there is a crossing of objects and verbs, so that you can't parenthesize it properly. This kind of triviality also happens in Swiss German, and it seems ridiculous to hang such a nontrivial statement as "language isn't context free" on such stupid examples both of the same type, in Swiss German and Dutch (see previous section). I think that the linguistics field must still be in Aristotle mode.Likebox (talk) 12:42, 27 February 2010 (UTC)

 * In particular, everything hinges on having the "want" there, which is really the main verb. The "help wash" should be thought of as a compound verb perhaps. You need nontrivial examples with many layers of nesting to figure out what the true pattern is, and human language doesn't naturally generate that.Likebox (talk) 12:49, 27 February 2010 (UTC)

Ambiguity, Passive Voice: needs improvement
Article currently states: "In later work (e.g. Chomsky 1981), the idea of formulating a grammar consisting of explicit rewrite rules was abandoned."

Could someone (who is more familiar than myself with the subject matter) please rewrite this sentence to eliminate the ambiguity and the passive voice. "Was abandoned" ... by who? Chomsky?

Karl gregory jones (talk) 19:02, 9 February 2011 (UTC)

Examples of possible overlap, and alternative explanations?
Article states: "It is hard to find cases of possible overlap and many such cases can be explained in an alternative way that doesn't assume overlap."

1. "Hard to find" sounds un-encyclopedic to my ear. Can someone rewrite this to sound more professional?

2. "Hard to find" means uncommon but extant. Can someone provide an example, or examples plural?

3. Can someone provide examples that have been explained in alternative ways?

Karl gregory jones (talk) 19:11, 9 February 2011 (UTC)

 * I wrote it, and I completely agree. If I knew the sources by heart I'd have added them but I'll see if I can find them. Rp (talk) 09:00, 10 February 2011 (UTC)

 * I wouldn't say it's hard to find cases of possible overlap, if you still allow alternative explanations. Just look at any sentence with an extra-posed relative clause, for example by replacing some words of your example: “[John met (a woman at a club yesterday] who had brown eyes)”.
 * Also, I doubt that "Natural human languages rarely allow overlapping". What about Non-English languages? What about spoken language? (“I saw that new car in an ad yesterday, with three wheels only!”) --Zahnradzacken (talk) 00:05, 15 February 2011 (UTC)

Minor question about an example
In the last paragraph of subsection "Proper CFGs" we find the following:

''This makes it clear that $$L(G) = \{ww^R:w\in\{a,b\}^*\}$$. The language is context-free, but as shown in Example 4.8, it is not regular.''

Should we remove this hard-coded reference to "Example 4.8"? Perhaps we might add an actual reference for this result.

(Sorry for the minor and possibly irrelevant points, I'm a newbie contributor.) — Preceding unsigned comment added by Marcelkcs (talk • contribs) 16:39, 29 May 2011 (UTC)

Formal Definition of a Context Free Language and the Empty Language
I don't think it makes sense to require that there is at least one production rule for the non-terminal S. All that counts is that the transitive closure of the production rules, filtered to terminals is taken, in defining the accepted language L(G). If there is no production rule for S, then we have obviously L(G) = {}, i.e. the accepted language is empty. This is not to be confused with L(G) = {eps}.

But there are also other context free grammars that also lead to empty languages. And there are such that have a rule for the start symbol S. For example the following grammar, has also an empty accepted language:

S --> S

So the requirement that thre is at least one rule for S, does not imply that the accepted language L(G) is non empty, so it doesn't make any sense.

Janburse (talk) 20:09, 20 June 2011 (UTC)

 * I agree. Where do you see this requirement?  It may be too early in the morning, but I can't find it in the article. Rp (talk) 07:29, 22 June 2011 (UTC)
 * I found it and removed the requirement. --Zahnradzacken (talk) 13:53, 23 June 2011 (UTC)

Notation
I'm currently studying CFGs in school; I got rather confused reading this article, when presented with this notation: S → SS   S → (S) S →

I hadn't seen a CFG presented that way before and I didn't know what it meant. Then later in the article I arrived at    S → bSbb | A A → aA | ε which is what I'm used to seeing.

After hunting through the article numerous times I finally searched the page for pipes and found "It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Hence the grammar above can be described more tersely as follows:" arbitrarily hidden under the "A regular grammar" section.

There absolutely needs to be a "Notation" section before the "Examples" section that clearly explains both styles of notation to the reader. Not explaining your first notation and switching to another notation midway through with an easily-missed warning is a recipe for confusion for those not fully familiar with the subject. I would write a notation section myself, but I don't feel I grasp the concept and terminology enough to write accurately about it. Some guy (talk) 05:52, 3 March 2013 (UTC)

 * Is there anything else you would like to read in a separate notation section? I moved the sentence you quoted up to the section Production rule notation, maybe that's enough for now? --Zahnradzacken (talk) 10:03, 23 March 2013 (UTC)

lead paragraph
The lead (or lede in Wiki-speak?) is terrible, IMO. The Background section does a better job of explaining what this is all about. I am a SW engineer, and remember a little about this from college many years ago, but that lead section did nothing in helping me remember the overall purpose and meaning of a CFG. I can't imagine how it could be expected to help a lay-person. Nerfer (talk) 17:18, 23 March 2020 (UTC)

 * I made an attempt to improve the lead, by replacing the former example by a C example. The problem is that there are two different audiences: a user knowing formal grammars in general should be told why these ones here are called context-free, while a user who is new to formal grammars should be told how a grammar works in general. - Jochen Burghardt (talk) 21:32, 23 March 2020 (UTC)

Misleading commas in examples
Until the section section "Well-formed parentheses", commas are used to separate production rules. But from there on, no commas are used! I think this should be done in an uniform way. — Preceding unsigned comment added by Doubletimer (talk • contribs) 17:55, 27 November 2020 (UTC)

Examples of languages that are not context free: proof is incorrect
I don't have editing experience, so I thought I'd bring this up here and let someone else address it. I buy that the language in this section (balanced but not properly nested strings of parentheses and brackets) is not context-free, but this cannot be shown through the Pumping Lemma. Indeed, any nonempty string in this language will contain either the pair '(' and ')' or the pair '[' and ']' - either of these pairs of substrings will satisfy the conclusion of the Pumping Lemma. The observation that this language contains the sublanguage (^n [^n )^n ]^n is irrelevant. The complexity of a language puts no bounds on the complexity of its subsets (e.g. the regular language (a)* of all strings of a's contains the subset {a^n | n is in your favorite non-recursively-enumerable set of natural numbers}). Mersenne44 (talk) 21:07, 26 September 2022 (UTC)
 * I think the standard proof is that L intersect (^* [^* )^* ]^* equals (^n [^m )^n ]^m. By closure under intersection with regular languages, if L were context free (^n [^m )^n ]^m would be context free. But it is not, by pumping. The bigger problem here, though, is that this section needs a published source. If we find one, we can follow whatever proof is used there. —David Eppstein (talk) 22:24, 26 September 2022 (UTC)
 * Oh I see - if you use (^n [^m )^n ]^m instead then it does make sense to just say L 'contains' this subfamily, since it witnesses unbounded distance between pumpable infixes. Thanks for clearing that up for me! I don't think there's a good proof that passes through (^n [^n )^n ]^n though, so that bit really should be changed. As far as citations go, might it be better to forego this example and just use L = a^n b^n c^n in this section? It's a pretty canonical example and appears in most published introductions to context-free languages that I've seen, plus the application of the pumping lemma is maybe a little more immediately obvious. Mersenne44 (talk) 00:01, 27 September 2022 (UTC)
 * Oh nevermind - I'm just tired. Same thing works with (^n [^n )^n ]^n - it witnesses the same thing as (^n [^m )^n ]^m. Ignore me - sorry! Mersenne44 (talk) 00:14, 27 September 2022 (UTC)

Avoid calling | the "pipe symbol"
Minor nitpick here.

The article says:

 * It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Rules $$\alpha\rightarrow \beta_1$$ and $$\alpha\rightarrow\beta_2$$ can hence be written as $$\alpha\rightarrow\beta_1\mid\beta_2$$. In this case, $$\beta_1$$ and $$\beta_2$$ are called the first and second alternative, respectively.

My suggestion is to avoid calling | the "pipe symbol", which might cause confusion to people interpreting it as the Bash pipe (https://en.wikipedia.org/wiki/Vertical_bar#Pipe) and think that $$\beta_1$$ is somehow fed into $$\beta_2$$.

Since the vertical bar (https://en.wikipedia.org/wiki/Vertical_bar) goes by a lot of other names, I think it would me more appropriate to refer to it as either: 130.192.232.228 (talk) 12:21, 30 September 2022 (UTC)
 * the "vertical bar",
 * or the "disjunction operator"/"alternative symbol" linking to https://en.wikipedia.org/wiki/Vertical_bar#Disjunction.

 * ✅: I agree that "pipe symbol" can be understood by Linux users only, and is misleading even to them. I changed both occurrences to "vertical bar". - Jochen Burghardt (talk) 14:27, 30 September 2022 (UTC)

Should "it is not proper since it includes an ε-production." be _explained_?
In the "Examples" section, the aforementioned sentence is confusing to me (I understand a lot of the rest of the page). The ε-production itself is defined in the context of the article earlier (further up) and no mention is made alluding to why there'd be [later] some improper something with it. It is only described what an ε-production is. I can't find any information that should somehow hint at or explain why "it is not proper". Transientdifficulties (talk) 20:10, 6 April 2023 (UTC)

 * I agree. Some definitions of CFGs (including Chomsky's) do not allow empty productions, and this should be explained, but it doesn't appear to be standard practice to call $\epsilon$-less grammars "proper". So the right approach is to add a paragraph explaining this and refer to it here. Rp (talk) 16:06, 11 April 2023 (UTC)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Talk:Context-free grammar