CNF

CNF may refer to:

Chomsky normal form

In formal language theory, a context-free grammar G is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form:

where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the context-free grammar G.

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form and has a size no larger than the square of the original grammar's size.

Converting a grammar to Chomsky normal form

To convert a grammar to Chomsky normal form, a sequence of simple transformations is applied in a certain order; this is described in most textbooks on automata theory. The presentation here follows Hopcroft, Ullman (1979), but is adapted to use the transformation names from Lange, Leiß (2009). Each of the following transformations establishes one of the properties required for Chomsky normal form.

Normal form

Normal form may refer to:

In formal language theory:

In logic:

In lambda calculus:

See also

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form

where is a single nonterminal symbol, and is a string of terminals and/or nonterminals ( can be empty). A formal grammar is considered "context free" when its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.

Such a grammar has long lists of words, and also rules on what types of words can be added in what order. Higher rules combine several lower rules to make a sentence. Such sentences will be grammatically correct, but may not have any meaning. Each rule has its own symbol, which can be replaced with symbols representing lower rules, which can be replaced with words.

This can also be done in reverse to check if a sentence is grammatically correct.

CIVI-DT

CIVI-DT, UHF digital channel 23, is a CTV Two owned-and-operated television station located in Victoria, British Columbia, Canada. The station is owned by Bell Media, as part of a twinstick with Vancouver-based CTV owned-and-operated station CIVT-DT (channel 32). CIVI maintains studio facilities located at the corner of Pandora Avenue and Broad Street across from Victoria City Hall, and its transmitter near Rockland. On cable, the station is also available on Shaw Cable channel 12 and in high definition on digital channel 212.

History

At the end of the 1990s, CHUM Limited only owned terrestrial television stations in the province of Ontario. Similarly, Craig Media only had stations in provinces within the Canadian Prairies. Both companies looked to expand their national presence, and both submitted a bid when the CRTC issued a call for applications for a new television station licence in Victoria; CHUM was awarded the licence in 2000. CIVI first signed on the air on October 4, 2001 as CHUM's first original station to be part of the NewNet television system.