Regular and Context-Free Languages (AQA A-Level Computer Science): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Regular language
Regular language
Language fully described using regular expressions
Context-free language
Context-free language
Language using BNF/syntax diagrams for complex nested structures
Regular vs context-free - key difference
Regular vs context-free - key difference
Regular: simple linear; Context-free: complex hierarchical
operator in regex
operator in regex
Zero or more of preceding element
operator in regex
operator in regex
One or more of preceding element
operator in regex
operator in regex
Zero or one of preceding element (optional)
Relationship between regex and FSM
Relationship between regex and FSM
Every regex can be represented as FSM and vice versa
Accepting state in FSM
Accepting state in FSM
State indicating valid string match (shown with double circle)
symbol in BNF
symbol in BNF
Means 'is defined as' or 'can be replaced with'
Ovals vs rectangles in syntax diagrams
Ovals vs rectangles in syntax diagrams
Ovals: terminals; Rectangles: non-terminals