Topic study hub
Context-free languages
Official AQA 7517 section 4.4.3.
0
Objectives
5
Flashcards
7
Questions
36 min
Study time
AqaA LevelComputer ScienceTheory of computation
Choose a revision tool
Start revising Context-free languages
Syllabus checklist
What you need to know
0 objective pages available
Backus-Naur Form (BNF)/syntax diagrams1 objectives
- Backus-Naur Form (BNF)/syntax diagrams: Be able to check language syntax by referring to BNF or syntax diagrams and formulate simple production rules. Be able to explain why BNF can represent some languages that cannot be represented using regular expressions.
Key terms
Production ruleRecursive rule
Exam tips
- Trace every alternative: When checking a string against BNF or a syntax diagram, follow the rules from the start symbol and consider each alternative and optional route.
Common mistakes
- Forgetting the stopping case: Include a base alternative, such as a single terminal or empty, so that a complete string can be generated.
Practice preview
- Given the production rules <letter> ::= "a" | "b" and <word> ::= <letter> | <letter> <word>, which string can be generated?
- A syntax diagram has a path from Start to End that passes through "A" and then an optional section containing "B". Which set contains all the strings accepted by this diagram?
- What does the symbol ::= usually mean in a BNF production rule?
Continue by objective
Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.
Related topics