Editing Formal Languages

<div style="background-color: #4B0082; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
{{BloomIntro}}
Formal Languages are the "Math of Meaning"—the study of "Rules" (Grammar) that define what makes a "String of Symbols" (a Sentence or Code) "Valid." While "Natural Languages" (English or French) are messy and ambiguous, "Formal Languages" (Python, Java, or Logic) are "Perfectly precise." Developed by **Noam Chomsky** in the 1950s, the "Chomsky Hierarchy" proved that there is a "Ladder of Complexity" in languages, and that different "Machines" are needed to understand them. From the "Regular Expressions" that search our text to the "Compilers" that translate human thoughts into binary, formal languages are the "Bridge" between "Human Ideas" and "Machine Action."
</div>

__TOC__

<div style="background-color: #000080; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Remembering</span> ==
* '''Formal Language''' — A set of "Strings" of symbols that are "Well-formed" according to a specific set of "Rules" (Grammar).
* '''Grammar''' — The set of "Production Rules" that tell you how to "Build" a valid sentence.
* '''Terminal Symbols''' — The "Actual words" or "Characters" in the language (e.g., 'A', 'B', '+', 'IF').
* '''Non-terminal Symbols''' — The "Placeholders" used in the rules (e.g., 'Noun', 'Verb', 'Expression').
* '''Derivation''' — The step-by-step "Process" of using the rules to "Create" a sentence.
* '''The Chomsky Hierarchy''':
# '''Type 0: Recursively Enumerable''' — The "Wild West" (Any rule). Needs a **Turing Machine**.
# '''Type 1: Context-Sensitive''' — The rules depend on what is "Around" the word. Needs a **Linear Bounded Automaton**.
# '''Type 2: Context-Free''' — The "Standard" for programming; rules are simple and "Nested." Needs a **Pushdown Automaton**.
# '''Type 3: Regular''' — The simplest: simple "Patterns" or "Sequences." Needs a **Finite State Machine**.
* '''Alphabet (Sigma)''' — The set of all "Legal Characters" in the language.
* '''String''' — A finite "Sequence" of symbols from the alphabet.
* '''Empty String (Epsilon)''' — A string with "Zero characters."
* '''Parser''' — A computer program that "Checks" if a sentence "Follows the Grammar."
</div>

<div style="background-color: #006400; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Understanding</span> ==
Formal languages are understood through '''Rules''' and '''Nesting'''.

'''1. The "Recipe" (Production Rules)''':
A grammar is like a "Recipe" for a sentence.
* Rule 1: **Sentence** → **Subject** + **Verb**.
* Rule 2: **Subject** → "The Cat" | "The Dog".
* Rule 3: **Verb** → "Runs" | "Sleeps".
* By "Applying" these rules, you can "Generate" thousands of valid sentences ("The Cat Sleeps," "The Dog Runs").
* A "Formal Language" is the "Total Set" of every sentence that can **ever** be made with those rules.

'''2. The "Mirror" (Context-Free Languages)''':
Regular languages are "Linear" (like a train). Context-free languages are "Symmetric" (like a mirror).
* A "Regular" language can handle: **AAAABBBB** (any number of As then any number of Bs).
* A "Context-Free" language can handle: **A{n} B{n}** (the number of As **must match** the number of Bs).
* To "Match" them, the machine needs a "Stack" (Memory) to "Count" the As as they go in. This is why "HTML tags" <div>...</div> or "Parentheses" ( ( ) ) are Context-Free.

'''3. The "Parser" (Understanding Code)''':
When you type "print('Hello')", the computer doesn't "Read" it like a human.
* It "Parses" it into a **Syntax Tree**.
* It checks: "Is 'print' a valid Terminal? Is there a '('? Is there a matching ')'?"
* If the "Formal Language Rules" are broken, you get a "Syntax Error."

'''The 'Chomsky Hierarchy' Insight'''': Noam Chomsky discovered that "Human Language" is much more complex than "Regular" or "Context-Free." He argued that humans have a "Universal Grammar" (Type 1 or Type 0) hard-wired in their brains, allowing us to "Understand" and "Create" infinite new sentences from birth. This linked "Linguistics" and "Computer Science" forever.
</div>

<div style="background-color: #8B0000; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Applying</span> ==
'''Modeling 'The Simple Grammar' (A script that generates valid 'Sentences'):'''
<syntaxhighlight lang="python">
import random

# Formal Grammar: S -> Subject Verb
grammar = {
    "Subject": ["Code", "Logic", "Data"],
    "Verb": ["Compiles", "Processes", "Crashes"]
}

def generate_formal_sentence():
    """
    Shows how 'Rules' generate 'Languages'.
    """
    subj = random.choice(grammar["Subject"])
    verb = random.choice(grammar["Verb"])
    return f"{subj} {verb}"

# Generating the 'Language' of this grammar
print(f"Sentence 1: {generate_formal_sentence()}")
print(f"Sentence 2: {generate_formal_sentence()}")
</syntaxhighlight>

; Language Landmarks
: '''Backus-Naur Form (BNF)''' → The "Standard Notation" used to "Write down" the rules of a programming language. It is the "Map" that all compiler-builders use.
: '''HTML and XML''' → "Markup Languages" that are "Context-Free." They rely on "Balanced Tags," which is why you can't parse HTML with simple "Regular Expressions" (it's too complex for an FSM).
: '''Natural Language Processing (NLP)''' → The attempt to treat "English" as a "Formal Language" so AIs can understand it. (This was the original goal of Chomsky, but English proved to be "Too Context-Sensitive" for simple math).
: '''The 'Ambiguous' Grammar''' → A "Bug" in a language where "One sentence" can have "Two Different Syntax Trees" (e.g., '1 + 2 * 3'—does it mean 7 or 9?). Formal languages must be "Unambiguous" to work in a computer.
</div>

<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Analyzing</span> ==
{| class="wikitable"
|+ Regular vs. Context-Free
! Feature !! Regular Language (Type 3) !! Context-Free Language (Type 2)
|-
| Rule Structure || Linear (A -> aB) || Recursive (A -> aAb)
|-
| Memory Needed || Zero || One Stack
|-
| Complexity || Simple (Search/Match) || High (Nesting/Parsing)
|-
| Example || Email Address Format || Python Source Code
|-
| Analogy || A 'String of Beads' || A 'Set of Russian Dolls'
|}

'''The Concept of "Turing-Completeness"''': Analyzing "Power." If a language is complex enough to "Simulate a Turing Machine" (Type 0), it is "Turing-Complete." Almost every programming language you use today is Type 0. This means you can "Write a Python interpreter in Python," which leads to the "Infinite Power" of modern computing.
</div>

<div style="background-color: #483D8B; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Evaluating</span> ==
Evaluating formal languages:
# '''The "Ambiguity" Curse''': Why is "Natural Language" so "Messy"? (Does the "Ambiguity" of English actually make us "More Creative," while the "Precision" of Code makes us "Robotic"?).
# '''Limits''': Can we write a "Formal Grammar" for "Art" or "Music"? (Are there "Rules" that define 'Beauty'?).
# '''Translation''': Why is it so "Hard" for a computer to "Translate" between two formal languages without losing the "Meaning" (Semantics)?
# '''Complexity''': As we move up the "Chomsky Hierarchy," the "Time" it takes to "Parse" the language "Explodes." Is "Simple" better than "Powerful"?
</div>

<div style="background-color: #2F4F4F; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Creating</span> ==
Future Frontiers:
# '''Self-Evolving Programming Languages''': A "Formal Language" that "Re-writes its own Grammar" to become "Easier to use" for a specific human, creating a "Personalized Bridge" to the machine.
# '''The 'Universal' Logic Language''': A single formal language for "Law," "Ethics," and "Contracts" that "Cannot be misunderstood," ending "Lawsuits" forever.
# '''DNA-Compiler''': A "Formal Language" for "Biology" that allows a doctor to "Write a Program" (e.g., 'Heal Bone') and "Compile" it into "DNA code" for the body.
# '''Natural-to-Formal AI''': An AI that can "Turn any English thought" into a "Perfectly Precise Formal Language," allowing "Non-programmers" to "Build anything."

[[Category:Mathematics]]
[[Category:Science]]
[[Category:Linguistics]]
[[Category:Computer Science]]
</div>